[R20C]两两不同 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $a$，你可以对数组进行以下操作：

• 选择一个下标 $i$（$1 \leq i \leq n$），并将 $a_i$ 的值增加 $1$。

你的目标是求出最少的操作次数，使得数组中的所有元素两两不同。换句话说，对于任意两个不同的下标 $i$ 和 $j$（$i \neq j$），都满足 $a_i \neq a_j$。

格式

输入格式

本题有多组测试数据。

第一行包含一个整数 $T$，表示测试数据的数量。

对于每组测试数据：

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

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

输出格式

对于每组数据，输出一行一个整数，表示使数组中所有元素两两不同的最少操作次数。

样例

样例输入 #1

1
4
1 2 2 3

样例输出 #1

2

样例解释 #1

可以对 $i = 3$ 操作 $2$ 次。此时数组为 $[1,2,4,3]$，满足题目要求的条件。

数据规模

对于 $50\%$ 的数据，$1 \leq n \leq 100$。

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