You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
In the easy version, the $$$a_i$$$ are in the range $$$[0, n]$$$; in the hard version, the $$$a_i$$$ are in the range $$$[-1, n]$$$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.

You are given an integer $$$n$$$ and an array $$$a_1, a_2 \dots, a_n$$$ of integers in the range $$$[0, n]$$$.

A permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$ is good if, for each $$$i$$$, the following condition is true:

- the number of values $$$\leq i$$$ in $$$[p_1, p_2, \dots, p_i]$$$ is exactly $$$a_i$$$.

Count the good permutations of $$$[1, 2, \dots, n]$$$, modulo $$$998\,244\,353$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$), which describe the conditions for a good permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single line containing the number of good permutations, modulo $$$998\,244\,353$$$.

## Examples
```input
5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15
```
```output
1
4
0
0
532305727
```

## Note
In the first test case, the only good permutation is $$$[1, 2, 3, 4, 5]$$$.

In the second test case, there are $$$4$$$ good permutations: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. For example, $$$[2, 1, 5, 6, 3, 4]$$$ is good because:

- $$$a_1 = 0$$$, and there are $$$0$$$ values $$$\leq 1$$$ in $$$[p_1] = [2]$$$;
- $$$a_2 = 2$$$, and there are $$$2$$$ values $$$\leq 2$$$ in $$$[p_1, p_2] = [2, 1]$$$;
- $$$a_3 = 2$$$, and there are $$$2$$$ values $$$\leq 3$$$ in $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;
- $$$a_4 = 2$$$, and there are $$$2$$$ values $$$\leq 4$$$ in $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;
- $$$a_5 = 4$$$, and there are $$$4$$$ values $$$\leq 5$$$ in $$$[p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]$$$;
- $$$a_6 = 6$$$, and there are $$$6$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]$$$.

In the third test case, there are no good permutations, because there are no permutations with $$$a_6 = 5$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$.

Now solve the problem and return the code.