题目描述

给定一个排列 $P=(P_1,P_2,\\cdots,P_N)$，其中包含了数字 $1$ 到 $N$。

可以执行以下操作零次或多次：

• 选择一个整数 $i$ ($1 \\leq i \\leq N-1$)。令 $v=\\max(P_i,P_{i+1})$ 并将 $P_i$ 和 $P_{i+1}$ 的值替换为 $v$。

问题是：在进行若干次操作后，$P$ 可能的排列有多少种？找到答案对 $998244353$ 取模。

约束条件

• $2 \\leq N \\leq 5000$
• $(P_1,P_2,\\cdots,P_N)$ 是 $(1,2,\\cdots,N)$ 的一个排列。
• 输入中的所有值均为整数。

输入格式

从标准输入中以以下格式获得输入：

$N$ $P_1$ $P_2$ $\\cdots$ $P_N$

输出格式

打印答案。

样例输入 1

3
1 3 2

样例输出 1

4

$P$ 可以变成的四种排列是 $(1,3,2)$, $(3,3,2)$, $(1,3,3)$ 和 $(3,3,3)$。

样例输入 2

4
2 1 3 4

样例输出 2

11

样例输入 3

10
4 9 6 3 8 10 1 2 7 5

样例输出 3

855