题目背景

学长们为参加比赛的所有选手准备了精美的小礼品。

大家可以期待一手是什么

题目描述

有n名同学，每人手中当前有$a_i$份礼品。现在要使得每人得到的礼品数量都相等。大家将进行如下操作

每人可将当前手中的物品传递给左右两边的同学（第一个同学的左右就是最后一名同学和第二名同学

每传递一份物品的消耗为一。求出最小消耗

输入格式

第一行一个整数n表示同学数量

第二行n个整数，表示当前同学手上的物品数

输出格式

一个整数，表示每人得到的礼品数量都相等的最小消耗

样例

输入样例

4
1 2 5 4

输出样例

4

数据说明

对于 $100\%$ 的数据 $1 \leq n\le 10^6$，$1 \leq a _ i \leq 1.5 \times 10 ^ 9$。