F2. Рифлёный массив (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 10^6$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Перестановка$$$^{\text{∗}}$$$ $$$b$$$ называется рифлёной перетасовкой перестановки $$$a$$$, если $$$|a| = |b|$$$ и существует $$$k$$$, где $$$1 \le k \lt |a|$$$, такое что $$$a_1,a_2,\ldots,a_k$$$ и $$$a_{k + 1},a_{k + 2},\ldots,a_{|a|}$$$ обе являются подпоследовательностями$$$^{\text{†}}$$$ массива $$$b$$$.

Например, $$$[\color{red}{1}, \color{blue}{4}, \color{blue}{5}, \color{red}{2}, \color{red}{3}, \color{blue}{6}]$$$ является рифлёной перетасовкой $$$[\color{red}{1}, \color{red}{2}, \color{red}{3}, \color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$$$, потому что мы можем выбрать $$$k = 3$$$, и обе $$$[\color{red}{1}, \color{red}{2}, \color{red}{3}]$$$ и $$$[\color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$$$ являются подпоследовательностями.

Вам дана перестановка $$$p$$$ длиной $$$n$$$, где некоторые значения заменены на $$$-1$$$. Определите количество способов заменить каждое $$$-1$$$ целым числом так, чтобы $$$p$$$ стала рифлёной перетасовкой $$$[1,2,\ldots,n]$$$ (отсортированной перестановки).

Так как количество способов может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — длина перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$ или $$$p_i = -1$$$) — элементы $$$p$$$. Все элементы $$$p$$$, которые не равны $$$-1$$$, различны.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите количество способов заполнить $$$p$$$ так, чтобы она была рифлёной перетасовкой $$$[1,2,\ldots,n]$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
7
5
-1 -1 -1 -1 -1
4
1 2 3 4
5
-1 -1 -1 2 -1
6
-1 3 2 1 -1 -1
18
11 -1 2 -1 -1 -1 -1 6 -1 -1 14 8 9 15 -1 -1 -1 -1
6
-1 3 -1 4 -1 5
3
-1 2 1
Выходные данные
27
1
6
0
32
0
0
Примечание

Возможные перестановки для третьего набора входных данных следующие:

  • $$$[\color{red}1, \color{blue}3, \color{blue}4, \color{red}2, \color{blue}5]$$$,
  • $$$[\color{red}1, \color{blue}4, \color{blue}5, \color{red}2, \color{red}3]$$$,
  • $$$[\color{blue}3, \color{red}1, \color{blue}4, \color{red}2, \color{blue}5]$$$,
  • $$$[\color{blue}3, \color{blue}4, \color{red}1, \color{red}2, \color{blue}5]$$$,
  • $$$[\color{blue}4, \color{red}1, \color{blue}5, \color{red}2, \color{red}3]$$$,
  • $$$[\color{blue}4, \color{blue}5, \color{red}1, \color{red}2, \color{red}3]$$$.