← 返回题目列表

Codeforces · 1249/A

A. 又一次分成小组

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

您是由 $$$n$$$ 学生组成的团体的教练。第 $$$i$$$ 个学生具有编程技能 $$$a_i$$$。所有学生都有独特的编程技能。您希望通过以下方式将他们分成团队:

- 没有两个学生 $$$i$$$ 和 $$$j$$$ 使得 $$$|a_i - a_j| = 1$$$ 属于同一团队(即同一团队中每对学生的技能差异严格大于$$$1$$$);
- 团队数量是尽可能少的。

您必须回答 $$$q$$$ 独立查询。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。然后是 $$$q$$$ 查询。

查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 查询中的学生人数。查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$,所有 $$$a_i$$$ 都是不同的),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的编程技能。

输出

对于每个查询,请在其上打印答案 - 如果没有两个学生 $$$i$$$ 和 $$$j$$$ 使得 $$$|a_i - a_j| 成立,则可以组建的最小团队数量= 1$$$ 可能属于同一团队(即同一团队中每对学生的技能差异严格大于$$$1$$$)

示例

输入 #1

4
4
2 10 1 20
2
3 6
5
2 3 4 99 100
1
42

输出 #1

2
1
2
1

注意

在示例的第一个查询中,有 $$$n=4$$$ 名学生,其技能为 $$$a=[2, 10, 1, 20]$$$。这里只有一个限制:第 $$$1$$$-st 和第 $$$3$$$-th 学生不能在同一个团队中(因为 $$$|a_1 - a_3|=|2-1|=1$$$)。可以将他们分成 $$$2$$$ 队:例如,学生 $$$1$$$、$$$2$$$ 和 $$$4$$$ 属于第一队,学生 $$$3$$$ 属于第二队。

在示例的第二个查询中,有 $$$n=2$$$ 名学生具有技能 $$$a=[3, 6]$$$。可以只组成一个由两名学生组成的团队。