题目描述

小猪 Pog 拥有一个长度为 $n$ 的排列 $p$。他打算进行恰好 $n$ 次操作，构造一个新的序列 $a$，初始为空。
每次操作中，Pog 可以选择以下两种之一：

• 移除 一个 $p$ 的最左端或最右端的一个元素。该元素不会加入 $a$。
• 查询 当前 $p$ 中的最小值，并将其追加到 $a$ 的末尾。该操作不会修改 $p$。

操作总次数必须恰好为 $n$。

Pog 想知道，通过不同的操作顺序，一共可以得到多少种不同的序列 $a$。
请输出该数量对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^6)$ —— 测试数据组数。

每个测试数据由两行组成：

• 第一行包含一个整数 $n$ $(1 \le n \le 10^6)$。
• 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，构成一个 $\{1,2,\ldots,n\}$ 的排列。

保证 $\sum n \le 10^6$。

输出格式

对于每组测试数据，输出一个整数，表示通过执行 $n$ 次操作可以创建的不同序列 $a$ 的数量，结果对 $998244353$ 取模。

输入输出样例 #1

输入 #1

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

输出 #1

4
6
15

说明/提示

以下是第二个测试用例中所有可能答案的列表。
我们用 L、R 表示从左侧和右侧的 移除 操作，用 Q 表示 查询 操作。

• $a = []$: L L L
• $a = [1]$: L R Q
• $a = [2]$: L L Q
• $a = [3]$: R R Q
• $a = [1, 1]$: Q L Q
• $a = [1, 1, 1]$: Q Q Q