33OJ
登录 注册

#P17493. [ICPC 2026 Wuhan I] Sort

    ID: 20221 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Sort

Problem Description

Given a permutation pp of length nn.

Each operation randomly chooses an integer ii with equal probability (1≤i≤n1 \le i \le n), and then sorts the prefix interval [1,i][1,i] and the suffix interval [i+1,n][i+1,n] of the permutation pp in ascending order, respectively. In particular, when i=ni=n, the suffix interval is empty, which is equivalent to sorting the entire permutation.

You need to find the expected number of operations required until the final permutation becomes completely sorted in ascending order (that is, pj=jp_j=j).

The answer should be taken modulo 998244353998244353.

Input Format

This problem contains multiple test cases.

The first line contains an integer TT (1≤T≤1001 \le T \le 100), the number of test cases.

For each test case:

  • The first line contains an integer nn (1≤n≤5001 \le n \le 500), the length of the permutation.
  • The second line contains nn integers p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n (1≤pj≤n1 \le p_j \le n), representing the given permutation pp. It is guaranteed that the given sequence is a permutation of 1∼n1\sim n.

It is guaranteed that the sum of nn over all test cases does not exceed 20002000.

Output Format

For each test case, output one line containing an integer, the expected number of operations modulo 998244353998244353.

3
3
3 1 2
2
2 1
5
3 2 5 1 4
748683267
2
670695427