Kevin and Puzzle
Contest: IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Difficulty rating: 1600
Tags: 2-sat, combinatorics, dp

Kevin enjoys logic puzzles.

He played a game with $$$n$$$ classmates who stand in a line. The $$$i$$$-th person from the left says that there are $$$a_i$$$ liars to their left (not including themselves).

Each classmate is either honest or a liar, with the restriction that no two liars can stand next to each other. Honest classmates always say the truth. Liars can say either the truth or lies, meaning their statements are considered unreliable.

Kevin wants to determine the number of distinct possible game configurations modulo $$$998\,244\,353$$$. Two configurations are considered different if at least one classmate is honest in one configuration and a liar in the other.

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 an integer $$$n$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$) — the number of classmates.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i \leq n$$$) — the number of liars to the left of the $$$i$$$-th person they claimed.

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 one integer — the number of distinct game configurations modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
We will use $$$\color{red}{\text{red}}$$$ to mark liars and $$$\color{blue}{\text{blue}}$$$ to mark honest people.

In the first test case, the only possible way is $$$(\color{red}{0},\color{blue}{1},\color{red}{2})$$$.

In the second test case, two possible ways are $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$$$ and $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$$$.

In the third test case, three possible ways are $$$(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{blue}{1},\color{red}{2})$$$.

Example input:
8
3
0 1 2
5
0 0 0 0 0
5
0 0 1 1 2
5
0 1 2 3 4
5
0 0 1 1 1
5
5 1 5 2 5
1
0
4
2 3 1 1

Example output:
1
2
3
0
4
1
2
0

Editorial:
For the $$$i$$$-th person, there are at most two possible cases:
• If they are honest, there are exactly $$$a_i$$$ liars to their left.
• If they are a liar, since two liars cannot stand next to each other, the $$$(i-1)$$$-th person must be honest. In this case, there are $$$a_{i-1} + 1$$$ liars to their left.
Let $$$dp_i$$$ represent the number of possible game configurations for the first $$$i$$$ people, where the $$$i$$$-th person is honest. The transitions are as follows:
• If the $$$(i-1)$$$-th person is honest, check if $$$a_i = a_{i-1}$$$. If true, add $$$dp_{i-1}$$$ to $$$dp_i$$$.
• If the $$$(i-1)$$$-th person is a liar, check if $$$a_i = a_{i-2} + 1$$$. If true, add $$$dp_{i-2}$$$ to $$$dp_i$$$.
The final answer is given by $$$dp_n + dp_{n-1}$$$.
Time complexity: $$$O(n)$$$.