P15866 [MX-X26-T2] "Cfz Round 7" Tap Tap Dance

The direction indicated by the compass, / the direction the compass points to. What the heart desires, / is where the heart is heading.

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$.

**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$.

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.

### 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