题目描述

$(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ が与えられます．

あなたは，以下の操作を $0$ 回以上行うことができます．

• 整数 $i$ ($1\ \leq\ i\ \leq\ N-1$) を選ぶ． $v=\max(P_i,P_{i+1})$ として，$P_i$ と $P_{i+1}$ の値を $v$ で置き換える．

操作後の $P$ としてあり得る数列が何通りあるかを $998244353$ で割った余りを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

答えを出力せよ．

题目大意

题目翻译

题目描述

给你一个 $1 \sim n$ 的排列 $P$ ,你可以进行若干次如下操作，也可以不进行操作。

• 每次选择一个整数 $i$ ($1\ \leq\ i\ \leq\ N-1$) ，使 $v=\max(P_i,P_{i+1})$ ，然后将 $P_i$ 和 $P_{i+1}$ 改为 $v$ 。

求问最后可能得到多少种不同的结果，答案对 $998244353$ 取模。

输入格式

第一行一行一个整数 $N$ 。

第二行 $N$ 个整数，第 $i$ 个数表示 $P_i$ 。

输出格式

一行一个整数，多少种不同的结果。

提示

数据范围与提示

• $2\ \leq\ N\ \leq\ 5000$
• $(P_1,P_2,\cdots,P_N)$ 为 $(1,2,\cdots,N)$ 的排列
• 输入均为整数

样例解释 1

操作后 $P$ 可能为 $(1,3,2),(3,3,2),(1,3,3),(3,3,3)$ 这 $4$ 种结果。

3
1 3 2

4

4
2 1 3 4

11

10
4 9 6 3 8 10 1 2 7 5

855

提示

制約

• $2\ \leq\ N\ \leq\ 5000$
• $(P_1,P_2,\cdots,P_N)$ は $(1,2,\cdots,N)$ の順列
• 入力される値はすべて整数である

Sample Explanation 1

操作後の $P$ としてありうる数列は $(1,3,2),(3,3,2),(1,3,3),(3,3,3)$ の $4$ 通りです．