续汉书曰：“孔融，字文举，鲁国人，孔子二十世孙也。高祖父尚，钜鹿太守。父宙，泰山都尉。”融别传曰：融四岁，与兄食梨，辄引小者。人问其故。答曰：“小儿，法当取小者。”

今天幼儿园有$n$个小朋友坐成一圈，每人有$a_i$个梨子。每人只向两侧的人传递梨子。每人每次传递一个梨子代价为$1$。

输入描述

第一行一个正整数$n \leq 987654321$，表示小朋友的个数。接下来$n$行，每行一个整数$a_i$，表示第$i$个小朋友得到的梨子的颗数。

输出描述

求使所有人获得均等梨子的最小代价。

输入样例1

4
1
2
5
4

输出样例1

4