AT_arc219_b.Reverse Permutation

You are given an integer $N$ and a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.

For a permutation $Q=(Q_1,Q_2,\ldots,Q_N)$ of $(1,2,\ldots,N)$, let $Q'=(Q_1',Q_2',\ldots,Q_N')$ be the lexicographically smallest permutation obtainable by performing the following operation exactly once:

• Choose a pair of integers $(l,r)$ satisfying $1\le l\le r\le N$, and reverse $Q_l,Q_{l+1},\ldots,Q_r$. More precisely, replace $Q$ with $(Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N)$.

Find the number, modulo $998244353$, of permutations $Q$ of $(1,2,\ldots,N)$ such that $Q'=P$.

You are given $T$ test cases; solve each of them.

给你一个整数 $N$ 和 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。

对于 $(1,2,\ldots,N)$ 的任意一个排列 $Q=(Q_1,Q_2,\ldots,Q_N)$，定义 $Q'=(Q_1',Q_2',\ldots,Q_N')$ 为对 $Q$ 恰好执行一次如下操作后所能得到的字典序最小的排列：

• 选择一对满足 $1\le l\le r\le N$ 的整数 $(l,r)$，并将子段 $Q_l,Q_{l+1},\ldots,Q_r$ 翻转。更准确地说，将 $Q$ 替换为
  $(Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N)$。

求满足 $Q'=P$ 的排列 $Q$（即 $(1,2,\ldots,N)$ 的排列）的个数，结果对 $998244353$ 取模。

你将收到 $T$ 组测试数据；请分别求解每组。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case.

For example, when $Q=(2,3,1)$, choosing $(l,r)=(1,3)$ gives $(1,3,2)$. No permutation lexicographically smaller than $(1,3,2)$ can be obtained, so we have $Q'=(1,3,2)$. Thus, $Q=(2,3,1)$ satisfies $Q'=P$.

There are two permutations $Q$ such that $Q'=P$: $Q=(2,3,1),(3,1,2)$.

Constraints

• $1\le T$
• $1\le N\le 5\times 10^5$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• The sum of $N$ over all test cases is at most $5\times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

例如，当 $Q=(2,3,1)$ 时，选择 $(l,r)=(1,3)$ 可得到 $(1,3,2)$。无法通过任何操作得到字典序比 $(1,3,2)$ 更小的排列，因此有 $Q'=(1,3,2)$。于是，$Q=(2,3,1)$ 满足 $Q'=P$。

满足 $Q'=P$ 的排列 $Q$ 共有两个：$Q=(2,3,1),\ (3,1,2)$。

约束条件

• $1\le T$
• $1\le N\le 5\times 10^5$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列。
• 所有测试用例的 $N$ 之和不超过 $5\times 10^5$。
• 所有输入值均为整数。