CF1790D Matryoshkas

套娃是一种木制玩具，外形为彩绘娃娃，内部可以放入一个更小的相似娃娃。 一组套娃包含一个或多个套娃，它们的尺寸是连续的正整数。因此，一组套娃可以用两个数字描述：$s$——该组中最小套娃的尺寸，$m$——该组中套娃的数量。换句话说，该组包含尺寸为 $s, s + 1, \dots, s + m - 1$ 的套娃，其中 $s,m > 0$。 你原本有一组或多组套娃。最近，你发现有人把你所有的套娃混在了一起，并记录下了一串套娃的尺寸——整数 $a_1, a_2, \dots, a_n$。 你已经不记得你原本有多少组套娃，所以你想找出你最初可能拥有的最少套娃组数。 例如，如果给定的序列是 $a=[2, 2, 3, 4, 3, 1]$，那么最初可能有 $2$ 组套娃： - 第一组包含 $4$ 个尺寸为 $[1, 2, 3, 4]$ 的套娃； - 第二组包含 $2$ 个尺寸为 $[2, 3]$ 的套娃。 根据给定的套娃尺寸序列 $a_1, a_2, \dots, a_n$，请确定最少需要多少组套娃才能组成该序列。 每一组套娃都必须被完整使用，即该组中的所有套娃都被用上。给定序列中的每个元素都必须恰好对应某一组中的一个套娃。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示所有套娃的总数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示这些套娃的尺寸。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

对于每个测试用例，输出一个整数 $k$，表示最少可能的套娃组数。

第一个测试用例已在题目描述中给出。 在第二个测试用例中，所有套娃可以组成一个最小尺寸为 $s=7$ 的套娃组。 在第三个测试用例中，每个套娃都只能单独成组。 由 ChatGPT 4.1 翻译