트랙 정리하기

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$)

위의 규칙에 따라 달구가 이동하는 총 거리를 출력한다.