투명 악어

시간 제한1초메모리 제한1024 MB

요약

각 위치의 발톱 자국 수가 주어질 때, 그 자국을 정확히 남기는 악어들의 공격력 합의 최솟값을 구합니다.

문제

"크아아아아" 악어 중에서도 최강인 투명 악어가 울부짖었다. 투명 악어는 튼튼하고 악어 중에서 최강이었다. 그러나 투명 코끼리, 투명 치타, 투명 아나콘다가 덤비면 졌다.

서기 ■■년, 세계는 대부분 망해서 차원이 무너지고 모든 것이 하나의 직선이 되었다. 이 직선 위의 늪지대에는 투명 악어들이 살고 있다. 투명 악어들은 보이지 않지만, 직선 위에 남은 발톱 자국을 보면 투명 악어가 있다는 것을 알 수 있다.

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

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

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

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

첫 줄에 늪지대의 좌표 범위를 나타내는 정수 $N$ ( $1 \le N \le 300,000$ )이 주어진다. 늪지대는 직선의 $[1, N]$ 범위에 펼쳐져 있다.

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

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

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