下发文件

题目描述

给定一个排列 $p$，你可以进行一次以下操作：

• 选择若干个不交的区间 $[l_1,r_1],\cdots,[l_k,r_k]$，然后对每个区间 $[l,r]$，把 $p_l,\cdots,p_r$ 升序排序。

问有多少种排列是可以得到的。答案对 $998244353$ 取模。

输入格式

从 sort.in 中读入数据。

本题有多组数据。第一行一个正整数 $T$ 表示数据组数。

第一行一个正整数 $n$ 表示排列长度。

第二行 $n$ 个正整数 $p_1,\cdots,p_n$ 表示给出的排列。

输出格式

输出到 sort.out 中。

对于每组数据，一行一个正整数表示答案。

样例 $1$ 输入

2
4
3 2 4 1
12
4 1 9 5 3 8 7 10 6 2 12 11

样例 $1$ 输出

6
300

样例 $1$ 解释

对于第一组数据：可以得到的排列有：3241 2341 1234 3124 3214 2314。共 $6$ 种。

大样例

其中 ex_sort4.in 满足排列随机生成，其他测试点不一定满足。

测试点约束

对于所有数据：$1\le n\le 2\times 10^5,1\le T\le 5$。

トリックハート (feat. 重音テト) - MIMI