F. Матожидание инверсий
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой размера $$$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
Примечание

В первом примере возможны две правильные перестановки:

  • $$$[3, 1, 2]$$$ — $$$2$$$ инверсии;
  • $$$[3, 2, 1]$$$ — $$$3$$$ инверсии.

Математическое ожидание равно $$$\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$$$.

Во втором примере нет $$$-1$$$, поэтому возможна единственная правильная перестановка — данная во входных данных. В ней $$$0$$$ инверсий.

В третьем примере возможны две правильные перестановки — одна с $$$0$$$ инверсий и одна с $$$1$$$ инверсией.