시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

There are n boxes on the circle. The boxes are numbered from 1 to n (1 ≤ n ≤ 1,000) in clockwise order. There are balls in the boxes, and the number of all the balls in the boxes is not greater than n. The balls should be displaced in such a way that in each box there remains no more than one ball. In one move we can shift a ball from one box to one of it's neighboring boxes.

Write a program that:

  • reads from the standard input the number of boxes n and the arrangement of balls in the boxes,
  • computes the minimal number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball,
  • writes the result to the standard output.

입력

In the first line of the standard input there is written one positive integer n — the number of boxes. In each of the following n lines there is written one nonnegative integer. In the i-th of these lines there is written the number of balls in the i-th box.

출력

Your program should write to the standard output one nonnegative integer — the number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball.

예제 입력 1

12
0
0
2
4
3
1
0
0
0
0
0
1

예제 출력 1

19