Background

The direction indicated by the compass, / the direction the compass points to.

What the heart desires, / is where the heart is heading.

Problem Description

Yuki has a sequence $a$ of length $n$.

Yuki defines one "Yuyu" operation as:

• Choose two integers $l, r$ such that $1 \le l \le r \le n$.
• Let the $\operatorname{mex}$ of $a_l \sim a_r$ be $x$. Delete the numbers in $a_l \sim a_r$ that are greater than $x$, and set $n$ to be the length of the sequence $a$ after this.

You need to find the minimum number of "Yuyu" operations needed to make the sequence $a$ as short as possible.

In this problem, the $\operatorname{mex}$ of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:

• $\operatorname{mex}(\{1,2,3\}) = 0$.
• $\operatorname{mex}(\{0\}) = 1$.
• $\operatorname{mex}(\{1,0,2,4\}) = 3$.

In particular, when the sequence is empty, its $\operatorname{mex}$ is $0$.

Input Format

This problem has multiple test cases.

The first line of the input contains two integers $c, t$, which represent the subtask number of this test point and the number of test cases. The sample satisfies $c = 0$.

Then the test cases follow one by one. For each test case:

• The first line contains an integer $n$.
• The second line contains $n$ integers $a_1, \dots, a_n$.

Output Format

For each test case, output one line containing one integer, which is the minimum number of "Yuyu" operations needed to make the sequence $a$ as short as possible.

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
2
1
3
2

Hint

Sample 1 Explanation

For the $1$st test case, you can directly choose $l = 1$ and $r = n$ to perform a "Yuyu" operation, which makes the sequence $a$ become $\{0\}$. It is easy to prove that $0$ cannot be deleted, so the length of $a$ is minimized at this point.

For the $2$nd test case, you can first choose $l = 1$ and $r = 1$ to perform a "Yuyu" operation, and the sequence $a$ becomes $\{0,3,3,1\}$. Then choose $l = 2$ and $r = 4$ to perform a "Yuyu" operation, and the sequence $a$ becomes $\{0\}$, reaching the minimum length.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test point.

For all test cases:

• $1 \le t \le 10^5$.
• $1 \le n \le 5 \cdot 10^5$, $\sum n \le 5 \cdot 10^5$.
• For all $1 \le i \le n$, $0 \le a_i \le 10^9$.

This problem uses bundled tests.

• Subtask 1 (18 points): $n \le 10$, $\sum n \le 10$.
• Subtask 2 (5 points): It is guaranteed that there is no $0$ in the sequence $a$.
• Subtask 3 (21 points): It is guaranteed that there is exactly one $0$ in the sequence $a$.
• Subtask 4 (24 points): For all positive odd numbers $i$ not greater than $n$, it is guaranteed that $a_i = 0$.
• Subtask 5 (32 points): No special constraints.

Translated by ChatGPT 5