题目描述

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

输入格式

小朋友个数 \(n\)，下面 \(n\) 行 \(a_i\)。

输出格式

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

输入输出样例 #1

输入 #1

4
1
2
5
4

输出 #1

4

说明/提示

对于 \(100\%\) 的数据 \(1 \leq n\le 10^6\)，\(1 \leq a _ i \leq 1.5 \times 10 ^ 9\)，\(\sum_{i=1}^{n}{a_i}\) 是 \(n\) 的倍数。