### 问题描述 固执的 Alice 总喜欢通过交换数组中相邻元素的方式来对数组进行非降序的排序，但神奇的是，她总能找到最小的交换次数使得数组变得有序。而敏锐的 Bob 觉得，通过这样的方式进行排序可能耗费的次数过多，因此他准备给 Alice 出排序题检测这一个结论。 现有一个长度为 $n$ 的数组 $nums$。Bob 先将其随机打乱，使得 $nums$ 的每个排列的出现概率都相同；接下来 Alice 用最小的相邻元素交换次数，将数组排列至非降序。设 Alice 进行的总交换次数为 $X$ 次，请你求出 $X$ 的期望是多少？ 可以证明，$X$ 的期望一定是有理数，同时可以表示为 $\frac{p}{q}(p\geq0, q>0, \gcd(p,q)=1, q \mod 998244353 \neq 0)$ 的形式，其中 $\gcd(p,q)$ 表示 $p,q$ 的最大公约数。请你输出 $p·q^{-1} \mod 998244353$，其中 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的逆元，满足 $q·q^{-1} \mod 998244353$ 且 $1 \leq q^{-1} < 998244353$ 。 ### 输入格式 第一行包含一个正整数 $n$，$n$ 表示数组的长度。 第二行包含 $n$ 个正整数 $nums_1, nums_2,..., nums_n$，用空格进行分隔，表示数组 $nums$ 中的每一个元素。 ### 输出格式 输出一行，表示所求的期望。 ### 样例输入 1 ```text 3 1 2 3 ``` ### 样例输出 1 ```text 499122178 ``` ### 说明 1 在样例中，数组被 Bob 打乱后的新数组可能为 $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$，每个排列发生的概率相等，对应的 Alice 进行的最小的交换次数分别为 $0,1,1,2,2,3$，因此期望为 $\frac{0+1+1+2+2+3}{6}=\frac{9}{2}$，因此输出的是 $9·2^{-1}=499122178$ 。 ### 样例输入 2 ```text 3 1 1 2 ``` ### 样例输出 2 ```text 1 ``` ### 说明 2 在样例中，数组被 Bob 打乱后的新数组可能为 $[1,1,2],[1,2,1],[2,1,1]$，每个排列发生的概率相等，对应的 Alice 进行的最小的交换次数分别为 $0,1,2$，因此期望为 $\frac{0+1+2}{3}=1$，因此输出的是 $1·1^{-1}=1$ 。 ### 评测数据规模 对于 $20\%$ 的评测数据，$1\leq n \leq 3\times 10^3$ 。 对于 $100\%$ 的评测数据，$1\leq n \leq 3\times 10^5$ 。 对于所有的测评数据，均满足 $1 \leq nums_i \leq 10^{18}$ 。