吃货套路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小铜很喜欢嗑瓜子,并且他相当讲究套路。这天小铜斥重金买下了一袋瓜子,按照嗑瓜子套路,他想要平分成n份来吃,于是他先把这袋瓜子随意地分成了n堆,并 把这n堆排成一排,第i堆有ai颗瓜子,对于每一堆瓜子,每次可以移动若干颗瓜子到相邻的一个瓜子堆里,例如第i堆瓜子可以移动若干颗至第i-1或第 i+1堆里,但是第1堆只能移动到第2堆,第n堆只能移动到第n-1堆。现在小铜想通过移动最少的次数使得每一堆的瓜子数量都相等,可是小铜是个吃货,不 会写程序,所以你帮他解决一下吧,他会用瓜子报答你的。
(友情提示:好好做题,多一些真诚,少一些套路)

Input

多组输入,对于每组输入第一行输入一个n(1 <= n <= 10^5 ),代表有n个瓜子堆。
第二行输入n个空格间隔的整数,第i个整数ai(1 <= ai <= 1000)代表第i堆瓜子的数量。

Output

对于每组数据输出一个整数,代表小铜最少需要移动的次数。如果无法使每一堆的瓜子数都相等,则输出整数-1。

Sample Input

5
1 2 3 4 5
3
2 3 3

Sample Output

4
-1

Hint

Source

2015级《程序设计基础II》计科软件期末上机考试1 - by Shannon