Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

math

probabilities

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Inversion Expectation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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

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

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}$$$.

Examples

Input

3 3 -1 -1

Output

499122179

Input

2 1 2

Output

0

Input

2 -1 -1

Output

499122177

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2024 11:58:19 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|