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

Для перестановки$$$^{\text{∗}}$$$ $$$q$$$ длины $$$m \ge 3$$$ определим $$$f(q)$$$ как последовательность $$$b$$$ длины $$$m - 2$$$, такую что $$$b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2})$$$ для всех $$$1 \le i \le m - 2$$$. Здесь $$$\operatorname{med}(x, y, z)$$$ обозначает второй по величине элемент среди $$$\{x, y, z\}$$$.

Вам дан массив $$$a$$$ длины $$$n$$$, где некоторые элементы могут быть равны $$$0$$$. Гарантируется, что $$$a$$$ содержит значения $$$1$$$ и $$$n$$$ (то есть существуют индексы $$$i, j$$$, такие что $$$a_i = 1$$$ и $$$a_j = n$$$).

Найдите количество перестановок $$$p$$$ длины $$$n$$$, удовлетворяющих следующим условиям:

  • $$$p$$$ согласована с $$$a$$$: для всех $$$1 \le i \le n$$$, если $$$a_i \neq 0$$$, то $$$p_i = a_i$$$.
  • Все элементы $$$f(p)$$$ различны.

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

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

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

Гарантируется, что все ненулевые элементы $$$a$$$ попарно различны. Также гарантируется, что $$$a$$$ содержит значения $$$1$$$ и $$$n$$$.

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

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

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

Пример
Входные данные
5
3
1 3 2
5
0 5 4 1 0
7
0 0 1 0 0 7 0
10
1 10 0 0 0 0 0 0 0 0
15
0 0 10 0 0 15 0 0 6 7 0 1 0 0 3
Выходные данные
1
0
10
1
4
Примечание

В первом наборе входных данных единственная перестановка, согласованная с входными данными, это $$$p = [1, 3, 2]$$$. Для неё $$$f(p) = [2]$$$, так как $$$\operatorname{med}(1, 3, 2) = 2$$$. Элементы $$$f(p)$$$ различны, поэтому эта перестановка является допустимой. Ответ равен $$$1$$$.

Во втором наборе входных данных есть две перестановки, согласованные с входными данными: $$$p = [3, 5, 4, 1, 2]$$$ и $$$p = [2, 5, 4, 1, 3]$$$.

  • Для $$$p = [3, 5, 4, 1, 2]$$$, $$$f(p) = [4, 4, 2]$$$.
  • Для $$$p = [2, 5, 4, 1, 3]$$$, $$$f(p) = [4, 4, 3]$$$.
В обоих случаях значение $$$4$$$ появляется дважды в $$$f(p)$$$. Таким образом, допустимых перестановок нет, и ответ равен $$$0$$$.