### 问题描述
固执的 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 中的每一个元素。
输出一行,表示所求的期望。
3
1 2 3
499122178
在样例中,数组被 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 。
3
1 1 2
1
在样例中,数组被 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} 。