A16666 | $Path Split$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 划分成最少多少个子序列。

输入 #1

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

C++ 编辑器

输入

输出