Problem Description

There are $ N $ islands arranged in a straight line. For $ 1≦i≦N-1 $, the $ i $th island from the left is adjacent to the $ (i+1) $th island.

Initially, the $ i $th island from the left has $ a_i $ residents. Takahashi wants all islands to have the same number of residents.

Takahashi can build bridges between two adjacent islands. Also, he can freely move residents between multiple islands that are directly or indirectly connected by bridges.

Find the minimum number of bridges that need to be built so that all islands have the same number of residents.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ $ .. $ $ a_N $

• The first line contains an integer $ N $ ($ 2≦N≦100 $), representing the number of islands.
• The second line contains integers $ a_i $ ($ 0≦a_i≦100 $), separated by spaces, indicating the number of residents on the $ i $th island from the left.

Output Format

Output the minimum number of bridges that need to be built so that all islands have the same number of residents. If it is impossible to achieve this by building any number of bridges, output -1 instead. End your output with a newline.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

2

Sample Input #2

5
2 0 0 0 3

Sample Output #2

3

Sample Input #3

2
0 99

Sample Output #3

-1

Sample Input #4

4
0 0 0 0

Sample Output #4

0

Notes/Hints

Sample Explanation 1

Bridges can be built as shown in the figure.

Sample Explanation 2

Bridges can be built as shown in the figure.

Sample Explanation 3

It is impossible to build bridges such that all islands have the same number of residents.

Sample Explanation 4

All islands already have the same number of residents from the beginning.

见题面 Input 部分

见题面 Output 部分