题目描述

有n个小朋友坐成一圈，每人有$a_i$颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为1。求使所有人获得均等糖果的最小代价。

输入描述

第一行有一个整数n，表示小朋友个数；

在接下来n行中，每行一个整数$a_i$。

输出描述

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

示例1

输入

4
1
2
5
4

输出

4

备注

对于$30\%$的数据，$n \leq 1000$； 对于$100\%$的数据，$n \leq 10^6$，保证答案可以用64位有符号整数存储。