問題文

$(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$ で割った余りを求めてください．

制約

• $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)$ の $4$ 通りです．

入力例 2

4
2 1 3 4

出力例 2

11

入力例 3

10
4 9 6 3 8 10 1 2 7 5

出力例 3

855