有n个小朋友站成一排，起初从左到右每个小朋友分别有a₁,a₂,...,aₙ颗糖果。 每一轮老师都会选择一个或多个有糖果的小朋友，他们会将自己的1颗糖果送给相邻的小朋友（左边或右边）。 请计算最少需要经过多少轮，才能使所有小朋友的糖果数量都相等；如果做不到，则输出-1。

样例说明

例1： n=3，初始糖果为[1,0,5]，最少需要3轮，过程如下：

1. 第一轮：第3个小朋友给第2个1颗，糖果变为[1,1,4]
2. 第二轮：第2个给第1个1颗、第3个给第2个1颗，糖果变为[2,1,3]
3. 第三轮：第3个给第2个1颗，糖果变为[2,2,2]

例2： n=3，初始糖果为[0,2,0]，总和为2无法被3整除，故输出-1。

输入描述

第一行输入一个整数n(1 ≤ n ≤ 10⁴)，表示小朋友的人数。 第二行输入n个整数a₁,a₂,...,aₙ(0 ≤ aᵢ ≤ 10⁵)，分别表示从左到右每个小朋友初始的糖果数量，整数之间以空格隔开。

输出描述

输出一个整数，表示最少需要的轮数；如果无法均分则输出-1。

样例输入

3
1 0 5

样例输出

3