A16569 | 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$ 取模。