CF2249B.Permutation Cuts

You are given an integer $n$ and an array $a$ of length $n-1$.

For a permutation$^{\text{∗}}$ $p$ of length $n$, define

$$v\_i=\\min\\left(\\max\_{1\\le j\\le i}p\_j, \\max\_{i+1\\le j\\le n}p\_j\\right),$$

where $1\le i\le n-1$.

In other words, cut the permutation between positions $i$ and $i+1$, take the maximum element on each side, and let $v_i$ be the smaller of these two values.

Your task is to count the number of permutations $p$ of length $n$ such that $v_i=a_i$ for each $1\le i\le n-1$.

Output the answer 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).

给你一个整数 $n$ 和一个长度为 $n-1$ 的数组 $a$。

对于一个长度为 $n$ 的排列$^{\text{∗}}$ $p$，定义

$$v\_i=\\min\\left(\\max\_{1\\le j\\le i}p\_j, \\max\_{i+1\\le j\\le n}p\_j\\right),$$

其中 $1\le i\le n-1$。

换言之，将排列在位置 $i$ 与 $i+1$ 之间切开，取左右两段各自的最大值，并令 $v_i$ 为这两个最大值中的较小者。

你的任务是计算满足对每个 $1\le i\le n-1$ 均有 $v_i=a_i$ 的长度为 $n$ 的排列 $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 one integer $n$ ($2\le n\le 10^6$) — the length of $p$.

The second line contains $n-1$ integers $a_1,a_2,\ldots,a_{n-1}$ ($1\le a_i\le n$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 10^6$）——即 $p$ 的长度。

第二行包含 $n-1$ 个整数 $a_1,a_2,\ldots,a_{n-1}$（$1\le a_i\le n$）——即数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, output one integer — the number of suitable permutations, modulo $998\,244\,353$.

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

In the first test case, both permutations $[1,2]$ and $[2,1]$ satisfy $v_1=1$.

In the second test case, the only suitable permutations are $[2,1,3]$ and $[3,1,2]$.

In the third test case, no suitable permutation exists.

在第一个测试用例中，排列 $[1,2]$ 和 $[2,1]$ 均满足 $v_1=1$。

在第二个测试用例中，唯一满足条件的排列是 $[2,1,3]$ 和 $[3,1,2]$。

在第三个测试用例中，不存在满足条件的排列。