You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

定义一个数组是“完美的”，当且仅当其所有值的平均数是一个整数。

现在给定有一个长度为 $n$ 的数组 $a$。为了让这个数组变得完美，你可以执行一次如下操作：

• 选择两个不同的下标 $i$ 和 $j$（$1 \leq i, j \leq n, i \neq j$）。
• 将第 $i$ 个元素 $a_i$ 的值修改为第 $j$ 个元素 $a_j$ 的值。

求总共有多少种不同的有序数对 $(i, j)$，在执行一次操作后，能使数组变得完美？

格式

输入格式

第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示数组 $a$ 的值。

输出格式

输出一个整数，表示满足条件的有序数对 $(i, j)$ 的数量。

样例

样例输入 #1

4
10 20 3 7

样例输出 #1

2

样例解释 #1

符合条件的有序对为 $(3,4)$ 和 $(4,3)$。

• 对于$(3,4)$：数组的和为 $10 + 20 + 7 + 7 = 44$，平均数为 $\frac{44}{4} = 11$，是整数，故符合条件。

• 对于$(4,3)$：数组的和为 $10 + 20 + 3 + 3 = 36$，平均数为 $\frac{36}{4} = 9$，是整数，故符合条件。

数据规模

对于 $40\%$ 的数据，$2 \leq n \leq 2000$。

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。