题目描述

有n个仓库沿环形排列，每个仓库中存放的货物数量可能不同。货物只能在相邻的仓库之间搬运，每搬运一件货物经过一个相邻仓库，搬运量增加1。已知货物总数能够被仓库数整除，请把货物搬运后使每个仓库中的货物数量相同，并求出最小搬运量。

输入格式

第一行输入一个整数n。

第二行输入n个整数，表示各个仓库中原有的货物数量。

输出格式

输出一个整数，表示使所有仓库货物数量相同所需的最小搬运量。

输入样例 1

5
17 9 14 16 4

输出样例 1

11

输入样例 2

1
877

输出样例 2

0

输入样例 3

3
33 35 37

输出样例 3

2

数据范围

• $1\le n\le 100000$。
• 每个仓库原有的货物数量 $a_i$ 满足 $0\le a_i\le 10^6$。
• 保证 $\sum a_i$ 能被 $n$ 整除，且答案在 64 位有符号整数范围内。