Problem Description

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

Input Format

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

Output Format

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

0 1
5
3 2 1 1 4

3

0 1
12
1 0 3 2 2 1 4 5 6 8 7 9

4

Hint

[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:

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

Translated by ChatGPT 5