상자

면접 대비

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

요약

상자 n개가 원형으로 놓여 있고 공의 총 개수는 n 이하이다. 이웃한 상자로 공을 옮겨 모든 상자에 공이 많아야 하나씩 있도록 할 때 최소 이동 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 누적 합, 수학, 구현
정답자: 아직 제출이 없습니다

문제

원을 따라 상자 $n$ 개가 놓여 있고, 시계 방향으로 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다 ( $1 \le n \le 1000$ ). 원형이므로 $1$ 번 상자와 $n$ 번 상자도 서로 이웃합니다. 일부 상자에는 공이 들어 있으며, 공의 총 개수는 $n$ 을 넘지 않습니다.

모든 상자에 공이 최대 한 개씩만 남도록 공을 옮기려고 합니다. 한 번의 이동으로 어떤 상자에 있는 공 하나를 이웃한 두 상자 중 하나로 옮길 수 있습니다.

각 상자에 공이 최대 한 개씩 남게 만드는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 상자의 개수 $n$ 이 주어집니다. 다음 $n$ 개의 줄에는 각각 음이 아닌 정수가 하나씩 주어지며, $i$ 번째 줄의 정수는 $i$ 번 상자에 들어 있는 공의 개수입니다. 공의 총 개수는 $n$ 을 넘지 않습니다.

출력

각 상자에 공이 최대 한 개씩 남도록 만드는 데 필요한 최소 이동 횟수를 음이 아닌 정수 하나로 출력합니다.

예제5

예제 1
입력
```
12
0
0
2
4
3
1
0
0
0
0
0
1
```
예상 출력
```
19
```
예제 2
입력
```
1
0
```
예상 출력
```
0
```
예제 3
입력
```
1
1
```
예상 출력
```
0
```
예제 4
입력
```
2
2
0
```
예상 출력
```
1
```
예제 5
입력
```
3
3
0
0
```
예상 출력
```
2
```