#P18290. Fast Bogosort

Fast Bogosort

Fast Bogosort

普通 Bogosort 反复将整个数组均匀随机打乱,再检查是否有序。下面考虑一种更快的算法,对 11 到 nn 的一个排列进行排序:

  1. 如果当前排列已经递增有序,结束算法。
  2. 否则,把排列划分成尽可能多个连续段。每段 [l,r][l,r] 中包含的数恰好是 l,l+1,…,rl,l+1,\ldots,r,各段互不重叠且覆盖整个排列。
  3. 对每个长度大于 11 的段 [l,r][l,r],调用一次 shuffle(l,r),将该段中的所有数均匀随机打乱。长度为 11 的段不调用此函数。
  4. 返回第 1 步,再次检查并重新划分。

给定初始排列,求算法结束前调用 shuffle(l,r) 的总次数的期望值。同一轮对不同段分别调用时,每次调用都需要计数。

输入格式

第一行包含一个整数 nn(1≤n≤1051\le n\le10^5)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,保证它们构成 11 到 nn 的一个排列。

输入只有一组数据。

输出格式

期望值可以表示为最简分数 P/QP/Q,题目保证 Q≢0(mod998244353)Q\not\equiv0\pmod{998244353}。输出唯一整数 RR,满足

$$0\le R<998244353,\qquad RQ\equiv P\pmod{998244353}.$$

样例 1

5
2 1 5 3 4
332748123

样例 2

10
4 2 3 1 6 5 9 7 10 8
453747445