当前没有测试数据。

G - 前序遍历

分数：$600$ 分

题目描述

有一棵有 $N$ 个顶点的有根树，顶点分别称为顶点 $1$，$2$，$\ldots$，$N$，以顶点 $1$ 为根。

我们从根节点开始进行深度优先搜索，并获得树的前序遍历序列：$P_1, P_2, \ldots, P_N$。
在搜索过程中，当当前顶点有多个孩子时，我们选择索引最小的未访问过的顶点。

求满足给定前序遍历序列的有根树的数量，对 $998244353$ 取模。
如果两棵有根树（有 $N$ 个顶点，以顶点 $1$ 为根）的非根顶点存在一个在两棵树中的父节点不同，则认为它们是不同的树。

约束条件

• $2 \leq N \leq 500$
• $1 \leq P_i\leq N$
• $P_1=1$
• 所有 $P_i$ 都是不同的。
• 输入中的所有数都是整数。

输入

输入从标准输入中给出，格式如下：

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

输出

输出满足给定前序遍历序列的有根树的数量，对 $998244353$ 取模。

4
1 2 4 3

3

满足前序遍历序列的有根树如下所示，一共有 $3$ 个，所以答案是 $3$。

注意下面这棵树不计算在内。因为，在顶点 $2$ 的孩子中，我们在访问顶点 $4$ 之前就访问了顶点 $3$，导致前序遍历序列为 $1,2,3,4$。

8
1 2 3 5 6 7 8 4

202