CF2165D Path Split

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。 你需要将 $a$ 划分为若干个子序列 $b_1, b_2, \ldots, b_k$，使得满足以下条件： - $a$ 中的每个元素恰好属于一个 $b_i$。 - 对于每个序列 $b_i$，设其元素为 $b_{i,1}, b_{i,2}, \ldots, b_{i,p_i}$。对于每一个 $1 \leq j < p_i$，都需满足 $|b_{i,j} - b_{i,j+1}| = 1$。 请计算 $a$ 至少需要划分成几个子序列。 注：“子序列”是指通过从原序列 $a$ 中删除若干（可能为零或全部）元素且不改变其余元素的相对顺序后所得的一个序列。

每组测试数据包含若干测试用例。第一行包含整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。 每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 10^6$），表示序列 $a$ 的长度。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i\leq 2n$），表示序列 $a$。 保证所有测试用例的 $n$ 之和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示将 $a$ 划分成最少多少个子序列。

在第一个测试用例中，可以将 $a$ 划分为子序列 $[1]$。显然无法划分得更少，因此答案是 $1$。 在第三个测试用例中，可以将 $a$ 划分为子序列 $[11,10,11,10]$、$[13]$、$[11]$、$[11]$、$[13]$。要注意 $[11,10,11,11,11,10]$ 不是一个有效子序列，因为 $|11-11|=0\neq1$。 由 ChatGPT 5 翻译