BOXES  Boxes
English  Vietnamese 
There are n boxes on the circle. The boxes are numbered from 1 to n (1<=n<=1000) in clock wise 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 in the standard output.
Input
The first line of the input file contains an integer t representing the number of test cases (t<=20). Then t test cases follows. Each test case has the following form:
 The first line contains one positive integer n  the number of boxes
 The second line contains n nonnegative integer separated by single spaces. The ith number is the number of balls in the ith box.
Output
For each test case, 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.
Example
Input: 1 12 0 0 2 4 3 1 0 0 0 0 0 1 Output: 19
hide comments
akaline:
20170707 10:19:44
23333 

sunrui2014:
20170707 05:14:22
gan


chenyushuo:
20150407 04:37:52
I got an Accepted! 
Added by:  Duc 
Date:  20050531 
Time limit:  7.273s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  III Polish Olympiad in Informatics, stage 3 