CF2061C.Kevin and Puzzle

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.

凯文喜欢逻辑谜题。

他和 $n$ 位同学玩了一个游戏，这些同学排成一列。从左往右数第 $i$ 位同学声称：在其左侧（不包括自己）有 $a_i$ 个说谎者。

每位同学要么是诚实者，要么是说谎者，且有一个限制条件：任意两个说谎者不能相邻。诚实者总是说真话；而说谎者则可能说真话也可能说假话，即他们的陈述不可靠。

凯文希望计算出满足条件的不同游戏配置总数，并对 $998\,244\,353$ 取模。若两种配置中至少存在一位同学在一种配置中是诚实者、而在另一种配置中是说谎者，则认为这两种配置不同。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leq n \leq 2 \cdot 10^5$）—— 同学的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \leq n$）—— 第 $i$ 个人所声称的其左侧说谎者的人数。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output one integer — the number of distinct game configurations modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——不同的游戏配置数目对 $998\,244\,353$ 取模的结果。

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

我们将用 $\color{red}{\text{红色}}$ 标记说谎者，用 $\color{blue}{\text{蓝色}}$ 标记诚实者。

在第一个测试用例中，唯一可能的情况是 $(\color{red}{0},\color{blue}{1},\color{red}{2})$。

在第二个测试用例中，两种可能的情况是 $(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$ 和 $(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$。

在第三个测试用例中，三种可能的情况是 $(\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})$。