← 返回题目列表

AtCoder · abc027_b

B. 岛和桥

中文机器翻译题面 查看原题

問題文

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

从一开始,所有岛屿的居民数量都相同。 我有一个