Inversion Expectation
Contest: Educational Codeforces Round 57 (Rated for Div. 2)
Difficulty rating: 2300
Tags: dp, math, probabilities

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 > j$$$ and $$$a_i < 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}$$$.

Input format:
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.

Output format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
3 -1 -1

Example output:
499122179

Example input:
2
1 2

Example output:
0

Editorial:
Let's break the problem into four general cases.
• Case 1. Inversions between two unknown numbers. Each pair of numbers can either be or inversion or not and the number of permutations for both cases is the same. Thus, the expected value of that is $$$\frac{cnt(-1) \cdot (cnt(-1) - 1)}{2} \cdot \frac 1 2$$$.
• Case 2 and 3. Inversions between the known and unknown number. Let's check the case with left number being unknown and right being known. The opposite will be done similarly. For each known number calculate the number of unknowns to the left of it $$$lft_x$$$ and the total number of unknowns greater than it $$$gt_x$$$. Then you'll need to put a greater number out of all possible to make an inversion. Add $$$lft_x \cdot \frac{gt_x}{cnt(-1)}$$$ to the answer.
• Case 4. Inversions between two known numbers. Just calculate that number ignoring all $$$-1$$$ and add it to answer.
Overall complexity: $$$O(n \log n)$$$ (for the lase case, all others are done in $$$O(n)$$$).