CF2190E.Median Permutation

For a permutation$^{\text{∗}}$ $q$ of size $m \ge 3$, define $f(q)$ to be a sequence $b$ of size $m - 2$ such that $b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2})$ for all $1 \le i \le m - 2$. Here, $\operatorname{med}(x, y, z)$ denotes the second smallest element among ${x, y, z}$.

You are given an array $a$ of size $n$, where some elements may be $0$. It is guaranteed that $a$ contains the values $1$ and $n$ (that is, there exist indices $i, j$ such that $a_i = 1$ and $a_j = n$).

Find the number of permutations $p$ of size $n$ satisfying the following conditions:

• $p$ is consistent with $a$: for all $1 \le i \le n$, if $a_i \neq 0$, then $p_i = a_i$.
• All elements of $f(p)$ are distinct.

Since the answer can be large, print it modulo $998\,244\,353$.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

对于一个长度为 $m \ge 3$ 的排列$^{\text{∗}}$ $q$，定义 $f(q)$ 为一个长度为 $m - 2$ 的序列 $b$，其中对所有 $1 \le i \le m - 2$，有 $b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2})$。此处，$\operatorname{med}(x, y, z)$ 表示集合 $\{x, y, z\}$ 中第二小的元素。

给定一个长度为 $n$ 的数组 $a$，其中某些元素可能为 $0$。保证 $a$ 中包含数值 $1$ 和 $n$（即存在下标 $i, j$，使得 $a_i = 1$ 且 $a_j = n$）。

请找出满足以下条件的长度为 $n$ 的排列 $p$ 的个数：

• $p$ 与 $a$ 一致：对所有 $1 \le i \le n$，若 $a_i \neq 0$，则 $p_i = a_i$；
• $f(p)$ 中的所有元素互不相同。

由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

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$ ($3 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$).

It is guaranteed that all non-zero elements of $a$ are pairwise distinct. It is also guaranteed that $a$ contains the values $1$ and $n$.

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$（$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$。

For each test case, print a single integer — the number of permutations $p$ satisfying the conditions, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——满足条件的排列 $p$ 的数量，对 $998\,244\,353$ 取模。

In the first example, the only permutation consistent with the input is $p = [1, 3, 2]$. We have $f(p) = [2]$, since $\operatorname{med}(1, 3, 2) = 2$. The elements of $f(p)$ are distinct, so this permutation is valid. The answer is $1$.

In the second example, there are two permutations consistent with the input: $p = [3, 5, 4, 1, 2]$ and $p = [2, 5, 4, 1, 3]$.

• For $p = [3, 5, 4, 1, 2]$, $f(p) = [4, 4, 2]$.
• For $p = [2, 5, 4, 1, 3]$, $f(p) = [4, 4, 3]$.

In both cases, the value $4$ appears twice in $f(p)$. Thus, there are no valid permutations, and the answer is $0$.

在第一个例子中，唯一与输入一致的排列是 $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$。