← 返回题目列表

Codeforces · 1598/C

C. 删除两个元素

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

Monocarp 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。我们将 $$$k$$$ 表示为这些元素的数学平均值(请注意,$$$k$$$ 可能不是整数)。

$$$n$$$ 元素数组的数学平均值是元素之和除以这些元素的数量(即总和除以 $$$n$$$)。

Monocarp 希望从 $$$a$$$ 中删除两个元素,以便剩余 $$$(n - 2)$$$ 元素的数学平均值仍然等于 $$$k$$$。

你的任务是计算位置对 $$$[i, j]$$$ ($$$i < j$$$) 的数量,这样如果这些位置上的元素被删除,则 $$$(n - 2)$$$ 剩余元素的数学平均值等于 $$$k$$$ (也就是说,它等于原始数组的 $$$n$$$ 元素的数学平均值$$$a$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组中的元素数量。

第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$),其中 $$$a_i$$$ 是数组的第 $$$i$$$ 元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

打印一个整数 — $$$[i, j]$$$ ($$$i < j$$$) 位置对的数量,这样如果删除这些位置上的元素,则 $$$(n - 2)$$$ 剩余元素的数学平均值等于 $$$k$$$ (即等于原始数组的 $$$n$$$ 元素的数学平均值$$$a$$$)。

示例

输入 #1

4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7

输出 #1

6
0
2
3

注意

在第一个示例中,可以删除任何一对元素,因为它们全部相等。

在第二个示例中,无法删除两个元素,因此数学平均值不会改变。

在第三个示例中,可以删除位置$$$1$$$和$$$3$$$上的元素,或者位置$$$4$$$和$$$5$$$上的元素。