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