题目描述

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

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

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

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

在本题中，长度为 $n$ 的排列是指由 $1, 2, \ldots, n$ 的构成的序列，其中每个整数恰好出现一次。

输入格式

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

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

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

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

输出格式

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

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

4
6
15

解释 #1

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

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