← 返回题目列表

Codeforces · 2114/C

C. 需要更多阵列

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

给定一个数组 $$$a$$$ 和 $$$n$$$ 整数。按非降序排序,即对所有 $$$1 \le i \lt n$$$ 为 $$$a_i \le a_{i + 1}$$$。

您可以从数组中删除任意数量的元素(包括根本不删除任何元素的选项),而无需更改剩余元素的顺序。删除后,将发生以下情况:

  • $$$a_1$$$ 写入新数组;
  • 如果 $$$a_1 + 1 \lt a_2$$$,则将 $$$a_2$$$ 写入新数组;否则,$$$a_2$$$ 被写入与 $$$a_1$$$ 相同的数组;
  • 如果 $$$a_2 + 1 \lt a_3$$$,则将 $$$a_3$$$ 写入新数组;否则,$$$a_3$$$ 被写入与 $$$a_2$$$ 相同的数组;
  • $$$\cdots$$$

例如,如果 $$$a=[1, 2, 4, 6]$$$,则:

  • $$$a_1 = 1$$$ 写入新数组,得到数组:$$$[1]$$$;
  • $$$a_1 + 1 = 2$$$,因此 $$$a_2 = 2$$$ 被添加到现有数组中,得到数组:$$$[1, 2]$$$;
  • $$$a_2 + 1 = 3$$$,因此 $$$a_3 = 4$$$ 被写入新数组,得到数组:$$$[1, 2]$$$ 和 $$$[4]$$$;
  • $$$a_3 + 1 = 5$$$,因此 $$$a_4 = 6$$$ 被写入新数组,从而生成数组:$$$[1, 2]$$$、$$$[4]$$$ 和 $$$[6]$$$。

您的任务是以所描述的算法创建尽可能多的数组的方式删除元素。如果从数组中删除所有元素,则不会创建新数组。

输入

输入的第一行包含一个整数 $$$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^6$$$, $$$a_i \le a_{i + 1}$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——通过删除任意(可能为零)数量的元素可以获得的数组的最大数量。

示例

输入
复制

6
6
1 2 3 4 5 6
3
1 2 3
4
1 2 2 4
1
2
3
1 4 8
2
1 1

输出
复制

3
2
2
1
3
1

注意

第一个例子中,可以去掉$$$a_3$$$和$$$a_5$$$,则$$$a=[1, 2, 4, 6]$$$,其组建数组的过程如语句所示。

在第二个例子中,需要删除$$$a_2$$$,之后$$$a = [1, 3]$$$,并且将写入数组$$$[1]$$$和$$$[3]$$$。

在第三个示例中,不需要删除;对于 $$$a = [1, 2, 2, 4]$$$,将写入数组 $$$[1, 2, 2]$$$ 和 $$$[4]$$$。