Matryoshkas

题意翻译

有一种玩具，每个玩具由一个序列组成。一个玩具可以表示为一个二元组 $(s,m)$，其中 $s,m>0$。其含义是这个玩具的序列长度为 $m$，元素为 $s,s+1,s+2,\cdots,s+m-1$。 ZYH 有很多个玩具，但是他不慎把所有玩具的元素乱序混合到了一起。例如玩具 $[1,2,3,4]$ 和玩具 $[2,3]$ 混合到一起后可能是 $[2,2,3,4,3,1]$。 给定混合后的序列 $a$，SA 想知道 ZYH 最初最少有多少个玩具。 多组数据，$1\leq T\leq 10^4,1\leq n \leq 2\times 10^5,1\leq a_i \leq 10^9,\sum n \leq 2\times 10^5$。 translated by @[StayAlone](https://www.luogu.com.cn/user/409236)

题目描述

Matryoshka is a wooden toy in the form of a painted doll, inside which you can put a similar doll of a smaller size. A set of nesting dolls contains one or more nesting dolls, their sizes are consecutive positive integers. Thus, a set of nesting dolls is described by two numbers: $ s $ — the size of a smallest nesting doll in a set and $ m $ — the number of dolls in a set. In other words, the set contains sizes of $ s, s + 1, \dots, s + m - 1 $ for some integer $ s $ and $ m $ ( $ s,m > 0 $ ). You had one or more sets of nesting dolls. Recently, you found that someone mixed all your sets in one and recorded a sequence of doll sizes — integers $ a_1, a_2, \dots, a_n $ . You do not remember how many sets you had, so you want to find the minimum number of sets that you could initially have. For example, if a given sequence is $ a=[2, 2, 3, 4, 3, 1] $ . Initially, there could be $ 2 $ sets: - the first set consisting of $ 4 $ nesting dolls with sizes $ [1, 2, 3, 4] $ ; - a second set consisting of $ 2 $ nesting dolls with sizes $ [2, 3] $ . According to a given sequence of sizes of nesting dolls $ a_1, a_2, \dots, a_n $ , determine the minimum number of nesting dolls that can make this sequence. Each set is completely used, so all its nesting dolls are used. Each element of a given sequence must correspond to exactly one doll from some set.

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the total number of matryoshkas that were in all sets. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the sizes of the matryoshkas. It is guaranteed that the sum of values of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, print one integer $ k $ — the minimum possible number of matryoshkas sets.

输入输出样例

输入样例 #1

10
6
2 2 3 4 3 1
5
11 8 7 10 9
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
1 1 4 4 2 3 2 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4

输出样例 #1

2
1
6
2
2
2
2
2
4
3

说明

The first test case is described in the problem statement. In the second test case, all matryoshkas could be part of the same set with minimum size $ s=7 $ . In the third test case, each matryoshka represents a separate set.

**题目大意：**
俄罗斯套娃是一组大小连续的正整数。每套套娃由两个数字描述：$ s $ 表示最小的套娃的大小，$ m $ 表示套娃的数量。也就是说，这套套娃包含大小为 $ s, s+1, \dots, s+m-1 $ 的套娃。给定一个混合后的套娃大小序列 $ a $，需要找出最初可能的最少的套娃套数。

**输入数据格式：**
第一行输入一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。每个测试用例包含两行，第一行是一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $），表示所有套娃的总数。第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le 10^9 $），表示套娃的大小。保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。

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

**输入输出样例：**
输入样例：
```
10
6
2 2 3 4 3 1
5
11 8 7 10 9
...
```
输出样例：
```
2
1
...
```
**说明：**
题目描述的第一个测试用例已经给出。第二个测试用例中，所有套娃可以属于同一个套娃套，最小的套娃大小为 $ s=7 $。第三个测试用例中，每个套娃代表一个单独的套娃套。**题目大意：** 俄罗斯套娃是一组大小连续的正整数。每套套娃由两个数字描述：$ s $ 表示最小的套娃的大小，$ m $ 表示套娃的数量。也就是说，这套套娃包含大小为 $ s, s+1, \dots, s+m-1 $ 的套娃。给定一个混合后的套娃大小序列 $ a $，需要找出最初可能的最少的套娃套数。 **输入数据格式：** 第一行输入一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。每个测试用例包含两行，第一行是一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $），表示所有套娃的总数。第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le 10^9 $），表示套娃的大小。保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。 **输出数据格式：** 对于每个测试用例，输出一个整数 $ k $，表示可能的最少的套娃套数。 **输入输出样例：** 输入样例： ``` 10 6 2 2 3 4 3 1 5 11 8 7 10 9 ... ``` 输出样例： ``` 2 1 ... ``` **说明：** 题目描述的第一个测试用例已经给出。第二个测试用例中，所有套娃可以属于同一个套娃套，最小的套娃大小为 $ s=7 $。第三个测试用例中，每个套娃代表一个单独的套娃套。