P17512 [ICPC 2026 Wuhan I] Sort（加强版）

与 [原题](https://www.luogu.com.cn/problem/P17493) 相比，加强版有更大的 $n$ 和 $\sum n$ 限制。

给定一个长度为 $n$ 的排列 $p$。 每次操作会等概率随机选择一个整数 $i$（$1 \le i \le n$），并将排列 $p$ 中的前缀区间 $[1,i]$ 和后缀区间 $[i+1,n]$ 分别进行升序排序。特别地，当 $i=n$ 时，后缀区间为空，即相当于对整个排列进行排序。 你需要求出，使得最终排列完全升序有序（即满足 $p_j=j$）所需要的期望操作次数。 答案对 $998244353$ 取模。

本题包含多组测试数据。 第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试数据组数。 对于每组测试数据： - 第一行包含一个整数 $n$（$1 \le n \le 10000$），表示排列的长度。 - 第二行包含 $n$ 个整数 $p_1,p_2,\cdots,p_n$（$1 \le p_j \le n$），表示给定的排列 $p$。保证给出的序列是一个 $1\sim n$ 的排列。 保证所有测试数据中 $n$ 的总和不超过 $20000$。

对于每组测试数据输出一行，包含一个整数，表示期望操作次数对 $998244353$ 取模后的结果。