4405. [CCPC 2026 HA] 灭霸排序 ||

Problem G. 灭霸排序

Input file: $\verb|standard input|$

Output file: $\verb|standard output|$

灭霸并不喜欢传统排序算法。

对于一个长度为 $m$ 的序列 $a_1, a_2, \dots, a_m$，定义一次“灭霸排序”操作如下：

• 如果当前序列已经严格递增，即满足 $a_1 \lt a_2 \lt \dots \lt a_m$，则算法立即结束。
• 否则，从当前序列的 $m$ 个位置中，等概率随机选择恰好 $\lfloor m/2 \rfloor$ 个位置删除，保留其余元素的相对顺序，然后继续对剩余序列执行同样的过程。

注意，上述删除操作中的 $m$ 指的是当前序列长度，而不是初始长度。

现在，给定一个长度为 $N$ 的排列 $p_1, p_2, \dots, p_N$。对该排列执行灭霸排序。

设最终剩余元素个数为 $X$。你需要求出 $\mathbb{E}[X]$，并将答案对 $998244353$ 取模后输出。

Input

第一行包含一个整数 $N$ ($1 \le N \le 3000$)。

第二行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$，表示一个长度为 $N$ 的排列。

Output

输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

更形式化地，若 $\mathbb{E}[X]$ 的最简分数表示为 $\displaystyle\frac{P}{Q}$，则你需要输出 $P \cdot Q^{-1} \pmod{998244353}$，其中 $Q^{-1}$ 表示 $Q$ 在模 $998244353$ 意义下的乘法逆元。

可以证明，在本题数据范围内，上述逆元一定存在。

Examples

3
3 1 2

332748119

5
5 1 2 3 4

2

Note

初始序列为 $[3, 1, 2]$，当前长度为 $3$，需要随机删除 $\lfloor 3/2 \rfloor = 1$ 个元素。

• 删除第 1 个元素后得到 $[1, 2]$，已经有序，最终剩余元素个数为 2。
• 删除第 2 个元素后得到 $[3, 2]$，仍然无序，接下来还会删除 1 个元素，最终剩余元素个数为 1。
• 删除第 3 个元素后得到 $[3, 1]$，同理最终剩余元素个数为 1。

因此 $E[X] = \frac{2+1+1}{3} = \frac{4}{3}$。

模 $998244353$ 意义下，$\frac{4}{3} \equiv 4 \cdot 3^{-1} \equiv 332748119 \pmod{998244353}$。