Codah ClubTrain. Submit. Improve.
Sign in
English
#0006A0

Boxes (easy)

There are boxes on the circle. The boxes are numbered from 1 to n (1 <= n <= 1000) 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.


InputThe first line contains one positive integer n - the number of boxes. The second line contains n nonnegative integer separated by single spaces. The i-th number is the number of balls in the i-th box.

OutputYour 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.

Input:
12
0 0 2 4 3 1 0 0 0 0 0 1
Output:19

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.