AT_arc228_c.Partially Sort

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$.

For a subsequence $x=(x_1,x_2,\dots,x_k)$ of $(1,2,\dots,N)$, let $f(x)$ denote the sequence obtained by the following procedure.

• Initialize the sequence $Q=(Q_1,Q_2,\dots,Q_N)$ with $Q = P$.
• Let $A=(A_1,A_2,\dots,A_k)$ be the sequence obtained by sorting $(Q_{x_1},Q_{x_2},\dots,Q_{x_k})$ in ascending order.
• For every integer $i$ satisfying $1 \le i \le k$, replace $Q_{x_i}$ with $A_i$. Let $f(x)$ be $Q$ at this point.

There are $2^N$ possible choices of $x$, including the empty sequence. Find the sum, modulo $998244353$, of the number of inversions of $f(x)$ over all those choices.

给你一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$。

对于 $(1,2,\dots,N)$ 的任意一个子序列 $x=(x_1,x_2,\dots,x_k)$，定义 $f(x)$ 为按如下步骤得到的序列：

• 初始化长度为 $N$ 的序列 $Q=(Q_1,Q_2,\dots,Q_N)$，令 $Q = P$。
• 将 $(Q_{x_1},Q_{x_2},\dots,Q_{x_k})$ 按升序排序，得到序列 $A=(A_1,A_2,\dots,A_k)$。
• 对每个满足 $1 \le i \le k$ 的整数 $i$，将 $Q_{x_i}$ 替换为 $A_i$。此时的 $Q$ 即为 $f(x)$。

共有 $2^N$ 种可能的 $x$（包括空序列）。对所有这些 $x$，求 $f(x)$ 的逆序对数量之和，并对 $998244353$ 取模。

The input is given from Standard Input in the following format:

$N$
$P_1\ P_2\ \dots\ P_N$

输入从标准输入中按以下格式给出：

$N$
$P_1\ P_2\ \dots\ P_N$

Output the answer.

输出答案。

Sample 1 Explanation:
$f(x)$ and its number of inversions for all eight possible choices of $x$ are as follows.

• For $x = ()$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$.
• For $x = (1)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$.
• For $x = (2)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$.
• For $x = (3)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$.
• For $x = (1,2)$, we have $f(x) = (1,3,2)$, and the number of inversions is $1$.
• For $x = (1,3)$, we have $f(x) = (2,1,3)$, and the number of inversions is $1$.
• For $x = (2,3)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$.
• For $x = (1,2,3)$, we have $f(x) = (1,2,3)$, and the number of inversions is $0$.

Thus, the answer is $2+2+2+2+1+1+2+0=12$.

Constraints

• $2 \le N \le 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• All input values are integers.

样例 1 解释：
$f(x)$ 及其在全部八种可能的 $x$ 取值下的逆序对数量如下所示。

• 当 $x = ()$ 时，有 $f(x) = (3,1,2)$，逆序对数量为 $2$。
• 当 $x = (1)$ 时，有 $f(x) = (3,1,2)$，逆序对数量为 $2$。
• 当 $x = (2)$ 时，有 $f(x) = (3,1,2)$，逆序对数量为 $2$。
• 当 $x = (3)$ 时，有 $f(x) = (3,1,2)$，逆序对数量为 $2$。
• 当 $x = (1,2)$ 时，有 $f(x) = (1,3,2)$，逆序对数量为 $1$。
• 当 $x = (1,3)$ 时，有 $f(x) = (2,1,3)$，逆序对数量为 $1$。
• 当 $x = (2,3)$ 时，有 $f(x) = (3,1,2)$，逆序对数量为 $2$。
• 当 $x = (1,2,3)$ 时，有 $f(x) = (1,2,3)$，逆序对数量为 $0$。

因此，答案为 $2+2+2+2+1+1+2+0=12$。

限制条件

• $2 \le N \le 2 \times 10^5$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列。
• 所有输入值均为整数。