B - 島と橋
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 個の島が横一列に並んでいる。 1≦i≦N-1 について、左から i 番目の島と i+1 番目の島は隣り合っている。
はじめ、左から i (1≦i≦N) 番目の島には a_i 人の住人が住んでいる。 高橋君はすべての島に同じ人数の住人が住むようにしたいと考えている。
高橋君は隣り合う 2 つの島の間に橋を架けることができる。 また、直接的または間接的に橋で結ばれた複数の島の間で、住人を自由に移動させることができる。
すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 .. a_N
- 1 行目には、島の個数を表す整数 N (2≦N≦100) が与えられる。
- 2 行目には、整数 a_i (0≦a_i≦100) が空白区切りで与えられる。これは、左から i 番目の島には a_i 人の住人が住んでいることを表す。
出力
すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を 1 行に出力せよ。
ただし、どのように橋を架けてもすべての島に同じ人数の住人が住むようにできないならば、代わりに -1 を出力せよ。
出力の末尾には改行を入れること。
入力例1
3 1 2 3
出力例1
2
図のように橋を架ければよい。
入力例2
5 2 0 0 0 3
出力例2
3
図のように橋を架ければよい。
入力例3
2 0 99
出力例3
-1
どのように橋を架けてもすべての島に同じ人数の住人が住むようにできない。
入力例4
4 0 0 0 0
出力例4
0
はじめからすべての島に同じ人数の住人が住んでいる。