← 返回题目列表

Codeforces · 1902/C

C. 插入并均衡

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

给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$,它的所有元素都是不同的。

首先,系统会要求您在该数组中再插入一个整数 $$$a_{n+1}$$$。 $$$a_{n+1}$$$ 不应等于 $$$a_1、a_2、\dots、a_n$$$ 中的任何一个。

然后,您必须使数组的所有元素相等。首先,您选择一个正整数 $$$x$$$ ($$$x > 0$$$)。在一项操作中,您将 $$$x$$$ 添加到数组的恰好一个元素。请注意,$$$x$$$ 对于所有操作都是相同的。

在选择 $$$a_{n+1}$$$ 和 $$$x$$$ 后,最少需要多少次操作才能使所有元素相等?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。所有 $$$a_i$$$ 都是不同的。

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

输出

对于每个测试用例,打印一个整数 - 在选择整数 $$$a_{n+1}$$$ 和 $$$x$$$ 后,使所有元素相等所需的最少操作数。

示例

输入 #1

3
3
1 2 3
5
1 -19 17 -3 -15
1
10

输出 #1

6
27
1

注意

在第一个测试用例中,可以选择$$$a_{n+1} = 4$$$,数组变为$$$[1, 2, 3, 4]$$$。然后选择 $$$x = 1$$$ 并对第一个元素应用操作 $$$3$$$ 次,对第二个元素应用操作 $$$2$$$ 次,对第三个元素应用操作 $$$1$$$ 次,对第四个元素应用操作 $$$0$$$ 次。

在第二个测试用例中,您可以选择 $$$a_{n+1} = 13, x = 4$$$。

在第三个测试用例中,您可以选择 $$$a_{n+1} = 9, x = 1$$$。然后对 $$$a_{n+1}$$$ 应用一次操作。