题目描述

在三沙群岛中有 n 个岛屿，编号分别为 1，2，…，n。每个岛屿上储存了一定数量的物资，这些物资总数必定是 n 的倍数。为了保障每个岛屿的物资供应平衡，需要设计一个物资调配方案。

移动规则如下：

1. 从编号为 1 的岛屿上取出的物资，只能运送到编号为 2 的岛屿上；
2. 从编号为 n 的岛屿上取出的物资，只能运送到编号为 n-1 的岛屿上；
3. 从其他岛屿上取出的物资，可以运送到相邻的左边或右边的岛屿上。

任务：找到一种移动方案，使得用最少的移动次数将所有岛屿上的物资数量调整到一样多。

输入格式

第一行一个整数 n。 第二行 n 个整数表示每个岛屿上的物资数量。

输出格式

一个整数，表示最小移动次数。

样例

输入样例

4
9 8 17 6

输出样例

3

样例解释

1. 3号->4号 移动 4 个物品 「9 8 13 10」
2. 3号->2号 移动 3 个物品 「9 11 10 10」
3. 2号->1号 移动 1 个物品 「10 10 10 10」

数据范围与提示

$n \leq 100$