32689번 - 트랙 정리하기

문제

DGIST 운동회가 끝난 다음 날, 달구는 쓰레기로 가득 찬 길이 $N$의 원형 육상 트랙을 정리하려고 한다.

원형 트랙은 둘레를 따라 시계 방향으로 1ドル$번 구역부터 $N$번 구역까지 총 $N$개의 구역이 1ドル$의 간격으로 나열되어 있다. 그중 $i$번 구역에는 쓰레기 $A_i$개가 쌓여 있으며, 달구는 모든 구역의 쓰레기를 치우고자 한다. 쓰레기를 치우던 달구는 지루함을 달래기 위해 다음과 같은 방식으로 쓰레기를 치우고자 한다.

• 달구는 쓰레기가 하나도 없는 1ドル$번 구역에서 트랙 정리를 시작하며, 시계 방향으로 이동한다.
• 만약 도달한 구역에 쓰레기가 없다면 이동 방향 그대로 계속 이동한다.
• 만약 도달한 구역에 쓰레기가 있다면 해당 구역의 쓰레기 한 개를 치운 뒤 이동 방향을 반대로 바꾼다.
• 모든 구역의 쓰레기를 모두 치우면 트랙 정리를 끝마치고 이동을 멈춘다.

이런 방식으로 트랙을 정리하던 달구는 문득 트랙 정리를 끝낼 때까지 얼마나 많은 거리를 이동해야 하는지 의문이 들었다! 달구를 위해, 달구가 이동해야 하는 총 거리를 알려주자.

입력

첫째 줄에 구역의 개수 $N$이 주어진다. $(2\le N\le 200,000円)$

둘째 줄에 각 구역에 있는 쓰레기의 개수를 나타내는 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0\le A_i \le 10,000円;$ $A_1=0)$

출력

주어진 조건에 따라 달구가 움직일 때, 이동해야 하는 총 거리를 출력한다.

제한

힌트