CF1928B Equalize

Vasya 有两个爱好——给数组加上排列和寻找出现次数最多的元素。最近，他发现了一个数组 $a$，并决定找出在给数组 $a$ 加上某个排列后，数组中相同数字出现次数的最大值。 更正式地说，Vasya 必须选择恰好一个长度为 $n$ 的排列 $p_1, p_2, p_3, \ldots, p_n$，然后按照规则 $a_i := a_i + p_i$ 修改数组 $a$ 的元素。之后，Vasya 统计数组 $a$ 中每个数字出现的次数，并取这些值的最大值。你需要求出他能获得的最大值。 $^{\dagger}$ 长度为 $n$ 的排列是由 $n$ 个 $1$ 到 $n$ 的不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

每个测试用例包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^4$），表示测试用例的组数。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。 每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示在加上某个排列后，数组中相同数字出现次数的最大值。

在第一个测试用例中，最优选择是 $p = [2, 1]$。操作后，数组 $a$ 变为 $[3, 3]$，此时数字 $3$ 出现了两次，所以答案是 $2$。 在第二个测试用例中，其中一种最优方案是 $p = [2, 3, 1, 4]$。操作后，数组 $a$ 变为 $[9, 4, 5, 5]$。由于数字 $5$ 出现了两次，所以答案是 $2$。 由 ChatGPT 4.1 翻译