CF1696B.NIT Destroys the Universe

For a collection of integers $S$, define $\operatorname{mex}(S)$ as the smallest non-negative integer that does not appear in $S$.

NIT, the cleaver, decides to destroy the universe. He is not so powerful as Thanos, so he can only destroy the universe by snapping his fingers several times.

The universe can be represented as a 1-indexed array $a$ of length $n$. When NIT snaps his fingers, he does the following operation on the array:

• He selects positive integers $l$ and $r$ such that $1\le l\le r\le n$. Let $w=\operatorname{mex}({a_l,a_{l+1},\dots,a_r})$. Then, for all $l\le i\le r$, set $a_i$ to $w$.

We say the universe is destroyed if and only if for all $1\le i\le n$, $a_i=0$ holds.

Find the minimum number of times NIT needs to snap his fingers to destroy the universe. That is, find the minimum number of operations NIT needs to perform to make all elements in the array equal to $0$.

对于一个整数集合 $S$，定义 $\operatorname{mex}(S)$ 为不在 $S$ 中出现的最小非负整数。

NIT，一位聪明的家伙，决定毁灭宇宙。他没有灭霸那么强大，因此只能通过多次打响指来毁灭宇宙。

宇宙可以表示为一个长度为 $n$ 的、下标从 $1$ 开始的数组 $a$。当 NIT 打响指时，他对该数组执行如下操作：

• 他选择正整数 $l$ 和 $r$，满足 $1\le l\le r\le n$。令 $w=\operatorname{mex}({a_l,a_{l+1},\dots,a_r})$。然后，对所有满足 $l\le i\le r$ 的下标 $i$，将 $a_i$ 赋值为 $w$。

我们称宇宙被毁灭，当且仅当对所有 $1\le i\le n$，均有 $a_i=0$ 成立。

求 NIT 毁灭宇宙所需的最少打响指次数。即，求使数组中所有元素均变为 $0$ 所需的最少操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\le n\le 10^5$).

The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($0\le a_i\le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1$, $a_2$, $\ldots$, $a_n$（$0\le a_i\le 10^9$）。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, print one integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first test case, we do $0$ operations and all elements in the array are already equal to $0$.

In the second test case, one optimal way is doing the operation with $l=2$, $r=5$.

In the third test case, one optimal way is doing the operation twice, respectively with $l=4$, $r=4$ and $l=2$, $r=6$.

In the fourth test case, one optimal way is doing the operation with $l=1$, $r=1$.

在第一个测试用例中，我们执行 $0$ 次操作，数组中的所有元素已经都等于 $0$。

在第二个测试用例中，一种最优方案是执行一次操作，其中 $l=2$，$r=5$。

在第三个测试用例中，一种最优方案是执行两次操作，分别取 $l=4$、$r=4$ 和 $l=2$、$r=6$。

在第四个测试用例中，一种最优方案是执行一次操作，其中 $l=1$，$r=1$。