给你一个 $$$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$$$ 可以划分成的子序列的最小数量。
示例
输入复制
71112811 13 10 11 11 11 13 1068 8 6 7 7 735 1 31011 14 14 13 12 14 12 10 14 1212
输出复制
1153371
注意
在第一个测试用例中,我们可以将 $$$a$$$ 划分为子序列 $$$[1]$$$。显然,我们不能将 $$$a$$$ 划分为更少的子序列;因此,$$$1$$$ 就是答案。
在第三个测试用例中,我们可以将 $$$a$$$ 划分为子序列 $$$[11,10,11,10],[13],[11],[11],[13]$$$。请注意 $$$[11,10,11,11,11,10]$$$ 不是有效序列,因为 $$$|11-11|=0\neq1$$$。