← 返回题目列表

Codeforces · 1613/D

D. MEX 序列

中文机器翻译题面 查看原题

让我们调用整数序列 $$$x_1, x_2, \dots, x_k$$$ MEX 正确,如果对于所有 $$$i$$$ ($$$1 \le i \le k$$$) $$$|x_i - \operatorname{MEX}(x_1, x_2, \dots, x_i)| \le 1$$$ 成立。其中 $$$\operatorname{MEX}(x_1, \dots, x_k)$$$ 是不属于集合 $$$x_1, \dots, x_k$$$ 的最小非负整数。例如,$$$\operatorname{MEX}(1, 0, 1, 3) = 2$$$ 和 $$$\operatorname{MEX}(2, 1, 5) = 0$$$。

给定一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。计算给定数组的非空 MEX 正确子序列的数量。子序列的数量可能非常大,因此将其打印为 $$$998244353$$$ 模。

注意:数组 $$$a$$$ 的子序列是满​​足约束 $$$1 \le i_1 < i_2 < \dots < i_m \le n$$$ 的序列 $$$[a_{i_1}, a_{i_2}, \dots, a_{i_m}]$$$。如果选择索引序列 $$$[i_1, i_2, \dots, i_m]$$$ 的两种不同方式产生相同的子序列,则应对所得子序列进行两次计数(即,如果索引序列 $$$[i_1, i_2, \dots, i_m]$$$ 不相同,则两个子序列不同)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 给定数组的非空 MEX 正确子序列的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3

输出 #1

4
2
31
7

注意

在第一个示例中,有效子序列是 $$$[0]$$$、$$$[1]$$$、$$$[0,1]$$$ 和 $$$[0,2]$$$。

在第二个示例中,有效子序列是 $$$[0]$$$ 和 $$$[1]$$$。

在第三个示例中,任何非空子序列都是有效的。