P15866 【MX-X26-T2】「Cfz Round 7」Tap Tap Dance

羅針盤の指す方角は　/　指南针所指的 心が望むもの　/　便是心之所向

Yuki 有一个长度为 $n$ 的序列 $a$。 Yuki 定义一次「鱼鱼」操作为： - 选择两个整数 $l,r$，满足 $1 \le l \le r \le n$； - 设 $a_l \sim a_r$ 的 $\operatorname{mex}$ 为 $x$，删除 $a_l \sim a_r$ 中大于 $x$ 的数，并将 $n$ 修改为此时序列 $a$ 的长度。 你需要求出使序列 $a$ 尽可能短所需的「鱼鱼」操作次数的最小值。 本题中，一个序列的 $\operatorname{mex}$ 为该序列中未出现过的最小非负整数，例如： - $\operatorname{mex}(\{1,2,3\})=0$； - $\operatorname{mex}(\{0\})=1$； - $\operatorname{mex}(\{1,0,2,4\})=3$； 特别地，当序列为空时，该序列的 $\operatorname{mex}$ 为 $0$。

**本题有多组测试数据。** 输入的第一行包含两个整数 $c,t$，分别表示该测试点所属的子任务编号和测试数据组数。样例满足 $c=0$。 接下来依次输入每组测试数据。对于每组测试数据： - 第一行包含一个整数 $n$。 - 第二行包含 $n$ 个整数 $a_1,\dots,a_n$。

对于每组测试数据，输出一行，包含一个整数，表示使序列 $a$ 尽可能短所需的「鱼鱼」操作次数的最小值。

### 样例 1 解释 对于第 $1$ 组测试数据，直接选择 $l=1$ 和 $r=n$ 进行「鱼鱼」操作即可使序列 $a$ 变成 $\{0\}$。容易证明 $0$ 无法被删除，此时序列 $a$ 的长度达到最小值。 对于第 $2$ 组测试数据，可以先选择 $l=1$ 和 $r=1$ 进行「鱼鱼」操作，此时序列 $a$ 变为 $\{0,3,3,1\}$，再选择 $l=2$ 和 $r=4$ 进行「鱼鱼」操作，此时序列 $a$ 变成 $\{0\}$，长度达到最小值。 ### 数据范围 设 $\sum n$ 表示单个测试点中 $n$ 的和。 对于所有测试数据，均有： - $1 \le t \le 10^5$； - $1 \le n \le 5 \cdot 10^5$，$\sum n \le 5\cdot 10^5$； - 对于所有 $1 \le i \le n$，均有 $0 \le a_i \le 10^9$。 **本题采用捆绑测试。** - Subtask 1（18 points）：$n \le 10$，$\sum n \le 10$。 - Subtask 2（5 points）：保证序列 $a$ 中不存在 $0$。 - Subtask 3（21 points）：保证序列 $a$ 中存在恰好一个 $0$。 - Subtask 4（24 points）：对于所有不大于 $n$ 的正奇数 $i$，保证 $a_i=0$。 - Subtask 5（32 points）：无特殊限制。