有 n 个小朋友坐成一圈，每人手里有 a_i 颗糖果。每个小朋友只能将糖果传递给他左边或右边相邻的小朋友。每传递一颗糖果的代价为 1。

现在需要让所有小朋友手中的糖果数量相等（题目保证糖果总数可以被 n 整除）。请你计算最少需要多少传递代价。

• 第一行包含一个整数 n （ 1 \le n \le 10^5 ），表示小朋友的人数。
• 接下来 n 行，每行一个整数 a_i （ 0 \le a_i \le 10^9 ），表示第 i 个小朋友初始拥有的糖果数。

数据保证 \sum a_i 能被 n 整除。

输出一个整数，表示最小传递代价。

样例说明

共有 4 个小朋友，糖果总数为 1+2+5+4=12 ，平均值为 12/4=3 。一种最优的传递方案：

• 第 1 个小朋友给第 4 个小朋友 1 颗糖（代价 1）；
• 第 3 个小朋友给第 2 个小朋友 2 颗糖（代价 2）；
• 第 3 个小朋友给第 4 个小朋友 1 颗糖（代价 1）。

总代价为 1+2+1=4 。（具体传递方式可能不同，但最小代价为 4。）

数据范围与约定

• 1 \le n \le 10^5
• 0 \le a_i \le 10^9
• 保证 \sum a_i 能被 n 整除。