B - 島と橋

B - 島と橋解説

実行時間制限: 2 sec / メモリ制限: 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 を出力せよ。出力の末尾には改行を入れること。

3
1 2 3

図のように橋を架ければよい。

5
2 0 0 0 3

図のように橋を架ければよい。

2
0 99

-1

どのように橋を架けてもすべての島に同じ人数の住人が住むようにできない。

4
0 0 0 0

はじめからすべての島に同じ人数の住人が住んでいる。