CF1096F.Inversion Expectation

A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array. An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i \gt j$ and $a_i \lt a_j$. For example, a permutation $[4, 1, 3, 2]$ contains $4$ inversions: $(2, 1)$, $(3, 1)$, $(4, 1)$, $(4, 3)$.

You are given a permutation $p$ of size $n$. However, the numbers on some positions are replaced by $-1$. Let the valid permutation be such a replacement of $-1$ in this sequence back to numbers from $1$ to $n$ in such a way that the resulting sequence is a permutation of size $n$.

The given sequence was turned into a valid permutation randomly with the equal probability of getting each valid permutation.

Calculate the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.

大小为 $n$ 的一个排列是指一个长度为 $n$ 的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。在排列 $p$ 中，一个逆序对（inversion）是指一对下标 $(i, j)$，满足 $i > j$ 且 $a_i < a_j$。例如，排列 $[4, 1, 3, 2]$ 包含 $4$ 个逆序对：$(2, 1)$、$(3, 1)$、$(4, 1)$、$(4, 3)$。

你被给定一个大小为 $n$ 的排列 $p$，但其中某些位置上的数字被替换成了 $-1$。我们称一个合法排列（valid permutation）为：将该序列中所有 $-1$ 替换为 $1$ 到 $n$ 中的某些数（每个数至多使用一次），使得最终得到的序列是一个大小为 $n$ 的排列。

已知该给定序列是通过等概率随机地选择所有可能的合法排列之一而得到的。

请计算所得合法排列中逆序对总数的期望值。

可以证明该期望值可表示为 $\frac{P}{Q}$ 的形式，其中 $P$ 和 $Q$ 是非负整数且 $Q \ne 0$。请输出 $P \cdot Q^{-1} \bmod 998244353$ 的值。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the sequence.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($-1 \le p_i \le n$, $p_i \ne 0$) — the initial sequence.

It is guaranteed that all elements not equal to $-1$ are pairwise distinct.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 序列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$-1 \le p_i \le n$，且 $p_i \ne 0$）—— 初始序列。

保证所有不等于 $-1$ 的元素两两互不相同。

Print a single integer — the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.

输出一个整数——结果中合法排列的逆序对总数的期望值。

可以证明该期望值可表示为 $\frac{P}{Q}$ 的形式，其中 $P$ 和 $Q$ 为非负整数且 $Q \ne 0$。请输出 $P \cdot Q^{-1} \pmod {998244353}$ 的值。

In the first example two resulting valid permutations are possible:

• $[3, 1, 2]$ — $2$ inversions;
• $[3, 2, 1]$ — $3$ inversions.

The expected value is $\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$.

In the second example no $-1$ are present, thus the only valid permutation is possible — the given one. It has $0$ inversions.

In the third example there are two resulting valid permutations — one with $0$ inversions and one with $1$ inversion.

在第一个例子中，存在两个可能的合法排列：

• $[3, 1, 2]$ — 含 $2$ 个逆序对；
• $[3, 2, 1]$ — 含 $3$ 个逆序对。

期望值为 $\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$。

在第二个例子中，输入中不含 $-1$，因此唯一可能的合法排列即为给定排列。该排列含有 $0$ 个逆序对。

在第三个例子中，存在两个可能的合法排列——其中一个含 $0$ 个逆序对，另一个含 $1$ 个逆序对。