CF1936E.Yet Yet Another Permutation Problem

You are given a permutation $p$ of length $n$.

Please count the number of permutations $q$ of length $n$ which satisfy the following:

• for each $1 \le i \lt n$, $\max(q_1,\ldots,q_i) \neq \max(p_1,\ldots,p_i)$.

Since the answer may be large, output the answer modulo $998\,244\,353$.

给你一个长度为 $n$ 的排列 $p$。

请计算满足以下条件的长度为 $n$ 的排列 $q$ 的个数：

• 对每个 $1 \le i \lt n$，均有 $\max(q_1,\ldots,q_i) \neq \max(p_1,\ldots,p_i)$。

由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single integer — the answer modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——答案对 $998\,244\,353$ 取模的结果。

In the first test case, $p = [2, 1]$. The only suitable $q$ is $[1, 2]$. Indeed, we need to satisfy the inequality $q_1 \neq p_1$. It only holds for $q = [1, 2]$.

In the second test case, $p = [1, 2, 3]$. So $q$ has to satisfy two inequalities: $q_1 \neq p_1$ and $\max(q_1, q_2) \neq \max(1, 2) = 2$. One can prove that this only holds for the following $3$ permutations:

• $q = [2, 3, 1]$: in this case $q_1 = 2 \neq 1$ and $\max(q_1, q_2) = 3 \neq 2$;
• $q = [3, 1, 2]$: in this case $q_1 = 3 \neq 1$ and $\max(q_1, q_2) = 3 \neq 2$;
• $q = [3, 2, 1]$: in this case $q_1 = 3 \neq 1$ and $\max(q_1, q_2) = 3 \neq 2$.

在第一个测试用例中，$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$，且 $\max(q_1, q_2) = 3 \neq 2$；
• $q = [3, 1, 2]$：此时 $q_1 = 3 \neq 1$，且 $\max(q_1, q_2) = 3 \neq 2$；
• $q = [3, 2, 1]$：此时 $q_1 = 3 \neq 1$，且 $\max(q_1, q_2) = 3 \neq 2$。