#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/C

Repovive

Equal Mex - Repovive Standard Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

8C. Equal Mex

1500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

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

You are given an array $a_1, a_2, \ldots, a_n$ .

You want to partition the array into one or more non-empty contiguous subarrays. A partition is called good if the mex of all subarrays in the partition are equal.

Count the number of good partitions modulo $998244353$ .

Two partitions are considered different if the positions of their cuts are different.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3
1 2 3

Case 2

4
0 1 0 1

Case 3

5
0 2 1 0 3

Case 4

6
0 1 0 1 0 1

Case 5

7
0 1 2 0 1 2 4

Explanation

Case 1

No segment contains $0$ , so every way of placing cuts is valid. For an array of length $3$ , there are $4$ partitions.

Case 2

The valid partitions are $[0,1,0,1]$ and $[0,1] [0,1]$ .

Case 3

The whole array has mex $4$ . Any non-trivial cut leaves a part without one of $0,1,2,3$ , so only the whole array works.

Case 4

Every part must contain both $0$ and $1$ . There are $5$ possible partitions.

Case 5

The valid partitions are $[0,1,2,0,1,2,4]$ and $[0,1,2] [0,1,2,4]$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

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

You are given an array $a_1, a_2, \ldots, a_n$ .

You want to partition the array into one or more non-empty contiguous subarrays. A partition is called good if the mex of all subarrays in the partition are equal.

Count the number of good partitions modulo $998244353$ .

Two partitions are considered different if the positions of their cuts are different.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

No segment contains $0$ , so every way of placing cuts is valid. For an array of length $3$ , there are $4$ partitions.

The valid partitions are $[0,1,0,1]$ and $[0,1] [0,1]$ .

The whole array has mex $4$ . Any non-trivial cut leaves a part without one of $0,1,2,3$ , so only the whole array works.

Every part must contain both $0$ and $1$ . There are $5$ possible partitions.

The valid partitions are $[0,1,2,0,1,2,4]$ and $[0,1,2] [0,1,2,4]$ .