这是问题的简单版本。版本之间的差异在于,在此版本中,您必须计算一个序列的值。只有解决了该问题的所有版本,您才能破解。
让我们定义一个算法来生成 $$$m+k$$$ 整数序列,如下所示:
- 首先,接收 $$$x$$$ 个 $$$m$$$ 整数序列作为输入。如果$$$k=0$$$,则立即终止并返回序列$$$x$$$。
- 然后,选择任意索引 $$$1 \le i \le |x|$$$ 并插入 $$$(x_i+1)$$$ 紧接着 元素$$$x_i$$$。
- 如果 $$$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$$$。
输出
对于每个测试用例,在单独的行上输出最短序列的长度。
示例
输入复制
551 2 3 4 551 3 5 7 951 2 5 6 571 2 4 5 3 7 899 8 9 2 3 4 4 5 3
输出复制
15343
注意
在第一个测试用例中,序列$$$[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$$$ 本身。