Perfect Choir

The Conductor of the choir is planning to take part in the famous Brazilian Choir Week, and therefore she wants the choir to rehearse a new song, described as follows:

• each member of the choir starts singing one note, and only changes the note when determined by the Conductor;
• at the end of each bar measure, the Conductor determines that exactly two singers change the note they are singing: one singer starts to sing the note immediately above the note she sang, and another singer starts to sing the note immediately below the note she sang;
• the song finishes at the end of the first bar measure in which all singers are singing the same note.

The Conductor already has several ideas of how to distribute the notes among choir members at the beginning of the song, in order to create the desired effect. However, she is worried about whether, given a note distribution for the singers, it is possible to reach the end of the song in the way she wants (all singing the same note). And, if that is possible, she wants to know the minimum number of bar measures the song can have. Can you help her?

Input 

The input contains several test cases. The first line of a test case contains an integer N indicating the number of members of the choir. Notes are indicated by integers. The second line contains N integers, indicating the note that each singer must sing at the beginning of the song. Notes are given in non-decreasing order.

Output 

For each test case, print a line containing a single integer indicating the minimum number of bar measures the song can have. If it is not possible to have all members singing the same note, then print the value `-1'.

Restrictions

• 2N10⁴
• -10⁵note_i10⁵ for 0iN - 1
• note_inote_i+1 for 0iN - 2

Sample Input 

3
1 2 3
4
3 6 9 12
6
1 2 3 4 5 723
5
10 10 10 10 10

Sample Output 

2
-1
601
1

---

題目描述：

每個歌唱者都有一開始的起音高度，指揮者一次可以讓兩個歌唱者分別上一度音與下一度音。
問指揮最少要幾次才能讓所有人都在同一度音。

題目解法：

算個平均數即可


#include <stdio.h>

int main() {
    int n, i, j;
    int A[10005];
    while(scanf("%d", &n) == 1) {
        int sum = 0;
        for(i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            sum += A[i];
        }
        if(sum%n) puts("-1");
        else {
            int ret = 1;
            int avg = sum/n;
            for(i = 0; i < n; i++)
                if(A[i] > avg)
                    ret += A[i]-avg;
            printf("%d\n", ret);
        }
    }
    return 0;
}