F2. Небольшая задачка про перестановки (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Andy Tunstall - MiniBoss
⠀

В простой версии задачи $$$a_i$$$ находятся в диапазоне $$$[0, n]$$$; в сложной версии $$$a_i$$$ находятся в диапазоне $$$[-1, n]$$$ и определение хорошей перестановки немного отличается. Вы можете делать взломы, только если обе версии задачи решены.

Вам дано целое число $$$n$$$ и массив $$$a_1, a_2, \dots, a_n$$$ целых чисел в диапазоне $$$[-1, n]$$$.

Перестановка $$$p_1, p_2, \dots, p_n$$$ в $$$[1, 2, \dots, n]$$$ называется хорошей, если для каждого $$$i$$$ верно следующее утверждение:

  • если $$$a_i \neq -1$$$, то количество значений $$$\leq i$$$ в $$$[p_1, p_2, \dots, p_i]$$$ в точности равно $$$a_i$$$.

Посчитайте количество хороших перестановок $$$[1, 2, \dots, n]$$$ по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le n$$$), которые описывают критерии хорошей перестановки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
10
5
-1 -1 -1 -1 -1
5
1 2 3 4 5
6
0 2 2 2 -1 -1
6
-1 -1 -1 -1 -1 5
6
-1 -1 3 2 -1 -1
15
0 0 -1 -1 -1 2 2 -1 -1 -1 -1 9 11 13 15
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15
Выходные данные
120
1
4
0
0
494403526
4
0
0
532305727
Примечание

В первом наборе входных данных все перестановки длины $$$5$$$ являются хорошими, поэтому существует $$$120$$$ хороших перестановок.

Во втором наборе входных данных единственной хорошей перестановкой является $$$[1, 2, 3, 4, 5]$$$.

В третьем наборе входных данных существует $$$4$$$ хороших перестановки: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. Например, $$$[2, 1, 5, 6, 3, 4]$$$ — хорошая, потому что:

  • $$$a_1 = 0$$$, и в $$$[p_1] = [2]$$$ есть $$$0$$$ значений $$$\leq 1$$$;
  • $$$a_2 = 2$$$, и есть $$$2$$$ значения $$$\leq 2$$$ в $$$[p_1, p_2] = [2, 1]$$$;
  • $$$a_3 = 2$$$, и есть $$$2$$$ значения $$$\leq 3$$$ в $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;
  • $$$a_4 = 2$$$, и есть $$$2$$$ значения $$$\leq 4$$$ в $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;
  • $$$a_5 = -1$$$, поэтому на $$$[p_1, p_2, p_3, p_4, p_5]$$$ нет ограничений;
  • $$$a_6 = -1$$$, поэтому на $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$ нет ограничений;