CF2201A1.Lost Civilization (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, you must compute a value for one sequence. You can hack only if you solved all versions of this problem.

Let's define an algorithm to generate a sequence of $m+k$ integers as follows:

1. First, receive a sequence $x$ of $m$ integers as input. If $k=0$, terminate immediately and return the sequence $x$.
2. Then, select any index $1 \le i \le |x|$ and insert $(x_i+1)$ immediately after the element $x_i$.
3. If $x$ contains exactly $m+k$ integers, terminate and return the sequence $x$. Otherwise, return to the second step.

Alice knows that this algorithm was used by an ancient civilization in order to hide their secrets safely. Alice wants to learn the knowledge that they wanted to hide, but it is not an easy job to infer the input from the output of the algorithm.

Given a sequence $a$ of $n$ integers, determine the length of the shortest sequence that could be given as an input for the algorithm to generate $a$.

这是该问题的简单版本。两个版本的区别在于：在本版本中，你只需对一个序列计算答案。只有当你解决了该问题的所有版本后，才可进行 Hack。

我们定义一种生成长度为 $m+k$ 的整数序列的算法如下：

1. 首先，接收一个长度为 $m$ 的整数序列 $x$ 作为输入。若 $k=0$，则立即终止并返回序列 $x$。
2. 然后，任选一个下标 $1 \le i \le |x|$，并在元素 $x_i$ 后立即插入 $(x_i+1)$。
3. 若当前序列 $x$ 恰好包含 $m+k$ 个整数，则终止并返回序列 $x$；否则，返回第二步继续执行。

Alice 知道，古代文明曾使用该算法来安全地隐藏他们的秘密。Alice 想要获取他们试图隐藏的知识，但根据算法输出反推输入并非易事。

给定一个长度为 $n$ 的整数序列 $a$，请确定能够通过该算法生成 $a$ 的最短可能输入序列的长度。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 300\,000$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the length of the shortest sequence on a separate line.

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

In the first test case, the sequence $[1]$ can generate the sequence $a=[1,2,3,4,5]$ by the following process:

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

In the second test case, the only sequence that can generate $a=[1,3,5,7,9]$ is $a$ itself.

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

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

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