CF2165D.Path Split

You are given a sequence of $n$ integers $a_1,a_2,\ldots,a_n$.

You would like to partition $a$ into several subsequences$^{\text{∗}}$ $b_1,b_2,\ldots,b_k$, satisfying the following conditions:

• Each element in $a$ belongs to exactly one of $b_i$.
• For each sequence $b_i$, let its elements be $b_{i,1},b_{i,2},\ldots,b_{i,p_i}$. For every $1\le j \lt p_i$, $|b_{i,j}-b_{i,j+1}|=1$ should hold.

Please calculate the minimum number of subsequences you can partition $a$ into.

$^{\text{∗}}$A sequence $b_i$ is a subsequence of a sequence $a$ if $b_i$ can be obtained from $a$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

给你一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

你希望将 $a$ 划分为若干个子序列$^{\text{∗}}$ $b_1,b_2,\ldots,b_k$，满足以下条件：

• $a$ 中的每个元素恰好属于某个 $b_i$；
• 对于每个子序列 $b_i$，设其元素为 $b_{i,1},b_{i,2},\ldots,b_{i,p_i}$，则对任意 $1\le j \lt p_i$，需满足 $|b_{i,j}-b_{i,j+1}|=1$。

请计算能将 $a$ 划分的最小子序列个数。

$^{\text{∗}}$ 序列 $b_i$ 是序列 $a$ 的一个子序列，如果 $b_i$ 可通过从 $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\le10^6$) — the length of the sequence $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le2n$) — the sequence $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le10^6$）——序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le2n$）——序列 $a$。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, print a single integer on one line — the minimum number of subsequences $a$ can be partitioned into.

对于每个测试用例，在一行中输出一个整数——序列 $a$ 可被划分成的最小子序列个数。

In the first test case, we can partition $a$ into subsequences $[1]$. It is obvious that we cannot partition $a$ into fewer subsequences; thus, $1$ is the answer.

In the third test case, we can partition $a$ into subsequences $[11,10,11,10],[13],[11],[11],[13]$. Please note that $[11,10,11,11,11,10]$ is not a valid sequence, since $|11-11|=0\neq1$.

在第一个测试用例中，我们可以将 $a$ 划分为子序列 $[1]$。显然，无法将 $a$ 划分为更少的子序列；因此答案为 $1$。

在第三个测试用例中，我们可以将 $a$ 划分为子序列 $[11,10,11,10],[13],[11],[11],[13]$。请注意，$[11,10,11,11,11,10]$ 不是一个合法的序列，因为 $|11-11|=0\neq1$。