← 返回题目列表

Codeforces · 2165/D

D. 路径分割

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

给你一个 $$$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$$$ 获得。

输入

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

输出

对于每个测试用例,在一行上打印一个整数 - $$$a$$$ 可以划分成的子序列的最小数量。

示例

输入
复制

7
1
1
1
2
8
11 13 10 11 11 11 13 10
6
8 8 6 7 7 7
3
5 1 3
10
11 14 14 13 12 14 12 10 14 12
1
2

输出
复制

1
1
5
3
3
7
1

注意

在第一个测试用例中,我们可以将 $$$a$$$ 划分为子序列 $$$[1]$$$。显然,我们不能将 $$$a$$$ 划分为更少的子序列;因此,$$$1$$$ 就是答案。

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