← 返回题目列表

AtCoder · arc219_b

B. 反向排列

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

分数: 400 点

问题陈述

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

对于排列 Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N),让 Q'=(Q_1',Q_2',\ldots,Q_N') 是通过执行以下操作一次可获得的按字典顺序排列的最小排列:

  • 选择一对整数 (l,r) 满意 1\le l\le r\le N,并反转 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).

求模数 998244353,排列 Q of (1,2,\ldots,N) 这样 Q'=P.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T
  • 1\le N\le 5\times 10^5
  • P 是一个排列 (1,2,\ldots,N).
  • 总和 N 所有测试用例最多 5\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

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

N
P_1 P_2 \ldots P_N

输出

按顺序输出测试用例的答案,以换行符分隔。


示例输入 1

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

示例输出 1

2
1
0
9

考虑第一个测试用例。

例如,当 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 这样 Q'=P: Q=(2,3,1),(3,1,2).