まず、\(Q\) から \(Q'\) を得る方法について考えます。

\(f(Q)\) を \(Q_i=i\) が \(1\le i\le k\) に対して成り立つような最大の \(k\) とします。

\(f(Q)=N\) の場合、\(Q=(1,2,\ldots,N)\) であり既に辞書順最小です。したがって、\(Q\) が変化しないように操作するのが最適です。

\(f(Q)<N\) の場合、\(i=f(Q)+1\) を考えることで \(f(Q)\) が増える操作は \(1\) つしか無いことが分かります。\(2\) つの順列 \(Q_1,Q_2\) に対し \(f(Q_1) < f(Q_2)\) が成り立つなら \(Q_1 < Q_2\) となることを用いると、この \(f(Q)\) が増える操作をするしかないことが分かります。

この事実を用いてこの問題を解きます。

\(f(Q)\) の値を固定します。この値は基本的に \(f(P)\) 未満です（例外として \(f(P)=N\) の場合に \(f(Q)=N\) もあり得ることに注意してください）。

\(f(P)=f(Q)=N\) のとき、あり得る \(P\) は \(1\) 通りです。

それ以外の場合、\(x=f(P)\) として \((l,r)=(x,*)\) に対して操作するべき \(P\) がそれぞれ \(1\) 通りずつ存在します。したがって、\(x=f(P),Q'=P\) を満たす \(Q\) は \(N-x\) 通り存在します。

以上をまとめると、求める答えは \(\displaystyle \sum_{x=1}^{f(P)}\max(1, N-x)\) になることが分かります。\(f(P)\) の値は \(O(N)\) で求まるので、全体として \(O(N)\) で答えを求めることができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    idx = 0
    ans = 0
    while idx != n and p[idx] == idx + 1:
        idx += 1
        ans += max(1, n - idx)
    print(ans % 998244353)

原案：sounansya