First, let us think about how to obtain \(Q'\) from \(Q\).

Let \(f(Q)\) be the maximum \(k\) such that \(Q_i = i\) holds for all \(1 \le i \le k\).

If \(f(Q) = N\), then \(Q = (1, 2, \ldots, N)\), which is already the lexicographically smallest. Thus, the optimal strategy is to perform an operation that does not change \(Q\).

If \(f(Q) < N\), by considering \(i = f(Q) + 1\), we can see that there is exactly one operation that increases \(f(Q)\). Using the fact that \(f(Q_1) < f(Q_2)\) implies \(Q_1 < Q_2\) for two permutations \(Q_1, Q_2\), we can conclude that we must perform this operation that increases \(f(Q)\).

We solve the problem using this fact.

Fix the value of \(f(Q)\). This value is basically less than \(f(P)\) (note that as an exception, when \(f(P) = N\), \(f(Q) = N\) is also possible).

When \(f(P) = f(Q) = N\), there is exactly one possible \(P\).

Otherwise, letting \(x = f(P)\), for each \((l, r) = (x, *)\) there is exactly one \(P\) where we should operate on this pair. Thus, there are \(N - x\) permutations \(Q\) satisfying \(x = f(P)\) and \(Q' = P\).

Summarizing the above, the answer is \(\displaystyle \sum_{x=1}^{f(P)} \max(1, N-x)\). The value of \(f(P)\) can be computed in \(O(N)\), so the entire answer can be computed in \(O(N)\).

By implementing the above appropriately, you can solve this problem.

Implementation example (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)

Proposed by: sounansya