2911. Lanes

单点时限: 10.0 sec

内存限制: 256 MB

There are S people swimming in the pool. At some point, the coach notices that their distribution over pool lanes is quite uneven, which is a nuisance for pool visitors. Changing the lane across ropes, however, poses a nuisance for a swimmer.
To form a nice distribution over the lanes the number of swimmers on each pair of adjacent lanes should differ by at most one. In particular, an empty lane should only be adjacent to another empty one or a lane occupied by only one swimmer.
Your task is to calculate the minimum number of swimmers’ lane changes needed to meet this condition.

输入格式

The first line of the input contains the only integer N — the number of lanes, 1 ≤ N ≤ 400. The next line contains N numbers separated by spaces: the number of swimmers in the first, second, . . . , Nth lane respectively. The sum of these numbers equals S (0 ≤ S ≤ 1 500).

输出格式

Output the minimum possible number of lane changes that are needed to meet a desired distribution.

样例

Input
3
8 0 2
3
8 5 7
Output
5
1

5 人解决,8 人已尝试。

37 份提交通过,共有 82 份提交。

7.3 EMB 奖励。

创建: 8 年,8 月前.

修改: 2 年,5 月前.

最后提交: 6 年,9 月前.

来源: N/A

题目标签