Source : 信息学奥赛一本通(提高篇)
Description
有 n 个小朋友坐成一圈,每人有 a颗糖果。每人只能给左右两边紧邻的人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。
Input

第一行有一个整数 n,表示小朋友个数;

在接下来 n行中,每行一个整数 ai

Output
输出使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
Sample Output
4
Hint
数据规模
对于 30%的数据,n≤1000

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