17444번 - 투명 악어

"크아아아아'' 악어중에서도 최강의 투명악어가 울부짓었따
투명악어는 졸라짱쎄서 악어중에서 최강이엇따
그러나 투명코끼리나 투명치타나 투명아나콘다가 덤비면 졋따

서기 ■■년, 세계는 대충 망해서 차원이 붕괴되고 하나의 직선 형태가 되었다. 이 직선 위의 늪지대에는 투명 악어들이 살고 있다. 투명 악어들은 투명해서 보이지 않지만, 직선 위에 찍히는 발톱 자국을 보고 투명 악어가 있다는 것을 알 수 있다.

뒤크는 어떤 투명하고 최강인 존재에게 아버지를 잃고, 복수를 위해 ■■년 동안 수련해 왔다. 그리고 마침내 투명한 존재 중 가장 약하다는 투명 악어 무리를 소탕하고 자기만족을 하기 위해 늪지대를 찾았다. 뒤크는 투명 악어에 대해 다음과 같은 정보를 공부해 왔다.

• 투명 악어에게는 하나의 앞발과 하나의 뒷발이 있다. 앞발은 발가락이 다섯 개지만, 뒷발은 발가락이 네 개인 대신 물갈퀴가 있다. 모든 발가락의 끝에는 발톱이 달려 있다.
• 투명 악어의 공격력은 앞발과 뒷발 사이의 거리와 같으며, 공격력이 0인 투명 악어는 없다. 즉 모든 투명 악어는 앞발과 뒷발이 다른 위치에 달려 있다.
• 투명 악어는 늪지대를 벗어나지 않으며, 정수 좌표의 위치만을 밟고 움직인다.

뒤크는 기세등등하게 늪지대에 왔지만, 직선 위에 찍힌 수많은 발톱 자국을 보고 살짝 겁먹었다. 그래서 투명 악어들의 공격력의 합이 최소 얼마일지 가늠해 보고, 그마저도 못 이길 것 같으면 빠르게 도망가서 수련을 더 하기로 했다.

뒤크를 위해 늪지대에 찍힌 발톱 자국을 보고 투명 악어 무리의 최소 공격력을 계산해 주자.

첫 줄에 늪지대의 좌표 범위를 의미하는 정수 N(1 ≤ N ≤ 300,000)이 주어진다. 이는 직선의 [1, N] 범위에 늪지대가 펼쳐져 있음을 의미한다.

두 번째 줄에 각 좌표에 찍혀 있는 발톱 자국을 의미하는 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수는 i 위치에 찍힌 발톱 자국의 수를 의미하며, 모든 정수는 0 이상 20 미만이다.

첫 줄에 투명 악어 무리의 최소 공격력을 출력한다. 투명 악어가 한 마리도 없는 경우는 0을, 투명 악어들만으로 늪지대에 찍힌 발톱 자국을 만들 수 없는 경우는 -1을 출력한다.

첫 번째 예제는 다음과 같이 악어가 배치되어 있을 때 공격력의 총합이 최소가 된다.

• 앞발이 2, 뒷발이 1 위치에 놓인 악어(공격력 1)
• 앞발이 4, 뒷발이 1 위치에 놓인 악어(공격력 3)
• 앞발이 4, 뒷발이 5 위치에 놓인 악어(공격력 1)
• 앞발이 5, 뒷발이 6 위치에 놓인 악어(공격력 1)