题目描述

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

输入格式：

小朋友个数n 下面n行 ai

输出格式：

求使所有人获得均等糖果的最小代价。

输入样例#1：

4
1
2
5
4

输出样例#1：

4

说明/提示

对于100% 的数据 n≤10^6。