P15457 [MX-X25-T1] "FeOI-5" Sequence Transformation.

Given a sequence $a$ of length $n$, repeatedly perform the following operations: 1. $\forall i\in[1,n]$, let $b_i$ be the $\text{mex}$ (the smallest non-negative integer that does not appear) of the set $\{a_1,a_2,a_3,\dots,a_i\}$; 2. $\forall i\in[1,n]$, update $a_i$ to $b_i$. Find how many different sequences $a$ will be generated during this process (including the original sequence, i.e., the sequence after round $0$). Two sequences $a,b$ of length $n$ are different if and only if $\exist i\in[1,n]$ such that $a_i\not=b_i$.

The first line contains two integers $c,T$, representing the subtask index of the test points (the samples guarantee that $c=0$) and the number of test cases. For each test case, the input consists of two lines: - The first line contains one integer $n$; - The second line contains $n$ integers describing the sequence $a$.

For each test case, output one line with one integer, representing the answer.

**[Sample 1 Explanation]** These are the results after the first few rounds of operations: ``` 3 2 1 1 4 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 ``` It is easy to see that afterwards, the sequence $a$ will keep alternating between the all-$1$ sequence and the all-$0$ sequence. Therefore, a total of $3$ sequences $a$ will be generated, so the answer is $3$. **[Sample 2 Explanation]** These are the results after the first few rounds of operations: ```cpp 1 0 3 2 2 1 4 5 6 8 7 9 0 2 2 4 4 4 5 6 7 7 9 10 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 ``` **[Constraints]** For all testdata, $1\le n,\sum n\le 10^6$, $0\le a_i\le n$, $1\le T\le 100$. | Subtask Index | $\sum n$ | Special Property | Score | | :-----------: | :--------: | :--------------: | :---: | | $1$ | $\le 5$ | None | $5$ | | $2$ | $\le 10$ | None | $10$ | | $3$ | $\le 10^6$ | $a_i\in\{0,1\}$ | $10$ | | $4$ | $\le 5000$ | None | $20$ | | $5$ | $\le 10^6$ | None | $55$ | Translated by ChatGPT 5