← 返回题目列表

Codeforces · 1913/D

D. 阵列崩溃

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

给定一个数组 $$$[p_1, p_2, \dots, p_n]$$$,其中所有元素都是不同的。

您可以用它执行多个(可能为零)操作。在一项操作中,您可以选择 $$$p$$$ 的连续子段并删除该子段中的所有元素(该子段上的最小元素除外)。例如,如果 $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ 并且您选择从 $$$3$$$ 第一个元素到第 $$$6$$$ 个元素的子段,则生成的数组为 $$$[3, 1, 2, 6]$$$。

如果可以使用多个(可能是零)上述操作从 $$$p$$$ 获取数组 $$$a$$$,则该数组称为可达数组。计算可达数组的数量,并以 $$$998244353$$$ 为模打印。

输入

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

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 可到达数组的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

3
2
2 1
4
2 4 1 3
5
10 2 6 3 4

输出 #1

2
6
12