AT_abc478_f.Min-First Search

For a tree $T$ with $N$ vertices called vertex $1$, vertex $2$, $\ldots$, vertex $N$, let $f(T)$ be the permutation $P$ of $(1,2,\ldots,N)$ obtained by the following procedure.

• Initially, let the sequence $P$ be the empty sequence $()$, and let the set $S$ be $\lbrace1\rbrace$.
• Repeat the following $N$ times.
  • Let $x$ be the minimum value of $S$. Remove $x$ from $S$, and append $x$ to the end of $P$.
  • Then, let $v_1, v_2, \ldots, v_k$ be the vertices adjacent to vertex $x$ in $T$. For $i=1,2,\ldots,k$, if $v _ i$ is not contained in $P$, add $v _ i$ to $S$.

You are given a permutation $Q=(Q _ 1,Q _ 2,\ldots,Q _ N)$ of $(1,2,\ldots,N)$. Find the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$. Here, two trees are distinguished when there exists a pair of vertices $(u,v)$ such that there is an edge between vertex $u$ and vertex $v$ in one tree and there is no edge in the other tree.

对于一棵包含 $N$ 个顶点的树 $T$，其顶点分别记为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。定义 $f(T)$ 为通过以下过程得到的 $(1,2,\ldots,N)$ 的一个排列 $P$：

• 初始时，令序列 $P$ 为空序列 $()$，集合 $S = \lbrace1\rbrace$。
• 重复以下操作 $N$ 次：
  • 令 $x$ 为集合 $S$ 中的最小值。将 $x$ 从 $S$ 中移除，并将其追加到序列 $P$ 的末尾。
  • 设 $v_1, v_2, \ldots, v_k$ 为树 $T$ 中与顶点 $x$ 相邻的所有顶点。对每个 $i = 1,2,\ldots,k$，若 $v_i$ 不在 $P$ 中，则将 $v_i$ 加入 $S$。

现给定 $(1,2,\ldots,N)$ 的一个排列 $Q = (Q_1, Q_2, \ldots, Q_N)$。求满足 $f(T) = Q$ 的树 $T$ 的数量（对 $998244353$ 取模）。此处，若存在一对顶点 $(u,v)$，使得某棵树中包含边 $(u,v)$ 而另一棵树中不包含该边，则认为这两棵树不同。

The input is given from Standard Input in the following format:

$N$
$Q _ 1$ $Q _ 2$ $\ldots$ $Q _ N$

输入从标准输入中按以下格式给出：

$N$
$Q _ 1$ $Q _ 2$ $\ldots$ $Q _ N$

Output the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$.

输出满足 $f(T)=Q$ 的树 $T$ 的数量，结果对 $998244353$ 取模。

Sample 1 Explanation:
For example, if $T$ is the following tree, then $f(T)=Q$.

The procedure to find $f(T)$ proceeds as shown in the following figure.

Including this tree, the following eight trees satisfy the condition.

Thus, output 8.

Sample 2 Explanation:
Output modulo $998244353$ the number of trees satisfying the condition.

Constraints

• $1\le N\le2\times10 ^ 5$
• $1\le Q _ i\le N\ (1\le i\le N)$
• $Q _ i\ne Q _ j\ (1\le i\lt j\le N)$
• $Q _ 1=1$
• All input values are integers.

样例 1 解释：
例如，若 $T$ 是如下所示的树，则 $f(T)=Q$。

求 $f(T)$ 的过程如以下图示所示。

包含该树在内，共有如下八棵满足条件的树。

因此，输出 8。

样例 2 解释：
输出满足条件的树的数量对 $998244353$ 取模的结果。

约束条件

• $1\le N\le2\times10 ^ 5$
• $1\le Q _ i\le N\ (1\le i\le N)$
• $Q _ i\ne Q _ j\ (1\le i\lt j\le N)$
• $Q _ 1=1$
• 所有输入值均为整数。