Tap Tap Dance

• 时间限制：$1.0$ 秒
• 空间限制：$512\text{ MB}$

题目背景

羅針盤の指す方角は　/　指南针所指的

心が望むもの　/　便是心之所向

题目描述

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 输入

0 5
4
2 0 2 6
5
1 0 3 3 1
5
1 1 8 3 1
6
1 0 3 1 0 2
7
4 0 9 8 1 3 8

样例 1 输出

1
2
1
3
2

样例 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）：无特殊限制。