CF2249B Permutation Cuts

给定一个整数 $n$ 和一个长度为 $n-1$ 的数组 $a$。 对于长度为 $n$ 的一个排列 $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$ 即这两个最大值里较小的那个。 你的任务是统计有多少个长度为 $n$ 的排列 $p$，满足对于每一个 $1\le i\le n-1$，都有 $v_i=a_i$。 请将答案对 $998\,244\,353$ 取模后输出。 一个长度为 $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$（$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$。

对于每个测试用例，输出一个整数，表示满足要求的排列个数，对 $998\,244\,353$ 取模。

在第一个用例中，排列 $[1,2]$ 和 $[2,1]$ 都满足 $v_1=1$。 在第二个用例中，唯一满足要求的排列是 $[2,1,3]$ 和 $[3,1,2]$。 在第三个用例中，没有满足条件的排列。 由 ChatGPT 5 翻译