题目描述

给定一个长为 $n$ 的序列 $\{a_i\}$。考虑一张 $n$ 个点的完全图。假设 $i<j$，那么 $i$ 和 $j$ 之间的边权为 $\operatorname{MEX}([a_i, a_{i+1}, \ldots, a_j])$。

假设 $b$ 是一个序列，我们定义 $\operatorname{MEX}(b)$ 为最小的未在 $b$ 中出现的自然数。例如：$\operatorname{MEX}([3,0,1]) = 2$，$\operatorname{MEX}([1,1,4,5,1,4]) = 0$。

求图中 $1$ 到 $n$ 的最短路长度。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表序列的长度；
• 接下来一行 $n$ 个正整数，代表序列 $[a_1,a_2,\ldots,a_n]$。

输出格式

对于每组数据，输出一行一个整数，代表该组数据中 $1$ 到 $n$ 的最短路长度。

4
3
0 1 2
3
1 0 3
5
1 0 2 1 0
6
1 1 4 5 1 4

2
2
3
0

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 200$，$1 \le n \le 200$；
• 对于另外 $30\%$ 的数据，$0 \le a_i \le 10$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 5 \cdot 10^5$，$1 \le \sum n \le 5 \cdot 10^5$，$0 \le a_i \le n$。