← 返回题目列表

Codeforces · 246/B

B. 增加和减少

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

Polycarpus 有一个数组,由 n 个整数 a1, a2, ..., an 组成。 Polycarpus 喜欢数组中的数字匹配。这就是为什么他希望数组中的数字尽可能多。为此,Polycarpus 多次执行以下操作:

- 他选择数组 ai、aj (i ≠ j) 的两个元素;
- 他同时将数字ai加1,将数字aj减1,即执行ai = ai + 1和aj = aj - 1。

给定的操作恰好更改了两个不同的数组元素。 Polycarpus 可以无限次地应用所描述的操作。

现在他想知道如果执行任意数量的此类操作,他最多可以获得多少个相等的数组元素。帮助波利卡波斯。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 数组大小。第二行包含空格分隔的整数 a1, a2, ..., an (|ai| ≤ 104) — 原始数组。

输出

打印一个整数——如果他执行任意数量的给定操作,他可以​​获得的相等数组元素的最大数量。

示例

输入 #1

2
2 1

输出 #1

1

输入 #2

3
1 4 1

输出 #2

3