← 返回题目列表

Codeforces · 2201/A1

A1. 失落的文明(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,您必须计算一个序列的值。只有解决了该问题的所有版本,您才能破解。

让我们定义一个算法来生成 $$$m+k$$$ 整数序列,如下所示:

  1. 首先,接收 $$$x$$$ 个 $$$m$$$ 整数序列作为输入。如果$$$k=0$$$,则立即终止并返回序列$$$x$$$。
  2. 然后,选择任意索引 $$$1 \le i \le |x|$$$ 并插入 $$$(x_i+1)$$$ 紧接着 元素$$$x_i$$$。
  3. 如果 $$$x$$$ 恰好包含 $$$m+k$$$ 整数,则终止并返回序列 $$$x$$$。否则,返回第二步。

爱丽丝知道这个算法是古代文明为了安全隐藏他们的秘密而使用的。 Alice想要学习他们想要隐藏的知识,但是从算法的输出推断输入并不是一件容易的事。

给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$,确定该序列的长度 最短 序列可以作为算法的输入给出,以生成 $$$a$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。

输出

对于每个测试用例,在单独的行上输出最短序列的长度。

示例

输入
复制

5
5
1 2 3 4 5
5
1 3 5 7 9
5
1 2 5 6 5
7
1 2 4 5 3 7 8
9
9 8 9 2 3 4 4 5 3

输出
复制

1
5
3
4
3

注意

在第一个测试用例中,序列$$$[1]$$$可以通过以下过程生成序列$$$a=[1,2,3,4,5]$$$:

$$[1] \到 [1,\color{red}{2}] \到 [1,2,\color{red}{3}] \到 [1,2,3,\color{red}{4}] \到 [1,2,3,4,\color{red}{5}]$$

在第二个测试用例中,可以生成 $$$a=[1,3,5,7,9]$$$ 的唯一序列是 $$$a$$$ 本身。