CF2190E Median Permutation

对于一个长度为 $m \ge 3$ 的排列 $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$ 且各不相同的数的序列。例如，$[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$ 取模。

在第一个样例中，唯一与输入一致的排列是 $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]$。 在这两种情况下，$f(p)$ 中值 $4$ 出现了两次。因此没有合法排列，答案是 $0$。 由 ChatGPT 5 翻译