BOXES - Boxes

题意翻译

### 题目大意 $n$ 个盒子围成一圈。 第 $i$ 个盒子初始时有 $a_i$ 个小球,小球数量总和满足 $\displaystyle\sum_{i=1}^{n}{a_i \leq n}$。 每次可以把一个小球从一个盒子移到相邻的两个盒子之一。求最少需要移动多少次,使得每个盒子中小球的个数不超过 $1$。 ### 输入格式 输入包含多组数据。 第一行 $1$ 个数 $t$ ,表示数据组数。 接下来每组数据包含 $2$ 行,第一行包括一个数 $n$ ,表示盒子数量,第二行包含 $n$ 个非负整数 $a_i$ ,第 $i$ 个数表示第 $i$ 个盒子里初始的小球数量。 ### 输出格式 输出包含 $t$ 行。 对于输入的每组数据,你需要输出 $1$ 行,包含 $1$ 个正整数,表示最少移动次数。

题目描述

[English](/problems/BOXES/en/) [Vietnamese](/problems/BOXES/vn/)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.

输入输出格式

输入格式


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 i-th number is the number of balls in the i-th box.

输出格式


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.

输入输出样例

输入样例 #1

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

输出样例 #1

19