E. Очередная очередная задача про перестановки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$ длины $$$n$$$.

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

  • для каждого $$$1 \le i < n$$$, $$$\max(q_1,\ldots,q_i) \neq \max(p_1,\ldots,p_i)$$$.

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

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

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

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

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

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

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

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

Пример
Входные данные
6
2
2 1
3
1 2 3
3
3 1 2
4
2 4 1 3
5
3 5 1 4 2
15
6 13 2 8 7 11 1 3 9 15 4 5 12 10 14
Выходные данные
1
3
2
4
18
424488915
Примечание

В первом наборе входных данных $$$p = [2, 1]$$$. Единственной подходящей $$$q$$$ является $$$[1, 2]$$$. Действительно, нам нужно выполнить неравенство $$$q_1 \neq p_1$$$. Оно выполнено только для $$$q = [1, 2]$$$.

Во втором наборе входных данных $$$p = [1, 2, 3]$$$. Так что $$$q$$$ должна удовлетворять двум неравенствам: $$$q_1 \neq p_1$$$ и $$$\max(q_1, q_2) \neq \max(1, 2) = 2$$$. Можно доказать, что это выполняется только для следующих $$$3$$$ перестановок:

  • $$$q = [2, 3, 1]$$$: в этом случае $$$q_1 = 2 \neq 1$$$ and $$$\max(q_1, q_2) = 3 \neq 2$$$;
  • $$$q = [3, 1, 2]$$$: в этом случае $$$q_1 = 3 \neq 1$$$ and $$$\max(q_1, q_2) = 3 \neq 2$$$;
  • $$$q = [3, 2, 1]$$$: в этом случае $$$q_1 = 3 \neq 1$$$ and $$$\max(q_1, q_2) = 3 \neq 2$$$.