Перестановкой размера $$$n$$$ называют такой массив из $$$n$$$ чисел, что все числа от $$$1$$$ до $$$n$$$ встречаются в нем ровно один раз. Инверсией в перестановке $$$p$$$ называют такую пару позиций $$$(i, j)$$$, что $$$i > j$$$ и $$$a_i < a_j$$$. Например, перестановка $$$[4, 1, 3, 2]$$$ содержит $$$4$$$ инверсии: $$$(2, 1)$$$, $$$(3, 1)$$$, $$$(4, 1)$$$, $$$(4, 3)$$$.
Задана перестановка $$$p$$$ размера $$$n$$$. Однако числа на некоторых позициях заменены на $$$-1$$$. Назовем правильной перестановкой такую замену $$$-1$$$ в этой последовательности обратно на числа от $$$1$$$ до $$$n$$$, что полученная последовательность является перестановкой размера $$$n$$$.
Заданная последовательность была преобразована в правильную перестановку случайным образом с одинаковой вероятностью получения каждой правильной перестановки.
Найдите математическое ожидание суммарного количества инверсий в полученной правильной перестановке.
Можно показать, что она может быть представлена в форме $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ — неотрицательные целые числа и $$$Q \ne 0$$$. Сообщите значение $$$P \cdot Q^{-1} \pmod {998244353}$$$.
В первой строке записано одно целое число $$$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$$$, попарно различны.
Выведите одно целое число — математическое ожидание суммарного количества инверсий в полученной правильной перестановке.
Можно показать, что она может быть представлена в форме $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ — неотрицательные целые числа и $$$Q \ne 0$$$. Сообщите значение $$$P \cdot Q^{-1} \pmod {998244353}$$$.
3 3 -1 -1
499122179
2 1 2
0
2 -1 -1
499122177
В первом примере возможны две правильные перестановки:
Математическое ожидание равно $$$\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$$$.
Во втором примере нет $$$-1$$$, поэтому возможна единственная правильная перестановка — данная во входных данных. В ней $$$0$$$ инверсий.
В третьем примере возможны две правильные перестановки — одна с $$$0$$$ инверсий и одна с $$$1$$$ инверсией.
Название |
---|