問題文

長さ $N$ の正整数の列 $a_1,a_2,\dots ,a_N$ が与えられます。
数列 $a$ には、$1$ から $N$ までの整数がそれぞれちょうど $1$ 回ずつ出現します。
つまり、数列 $a$ は $1,2,\dots ,N$ の順列です。

数列 $a$ に対して以下の操作を好きな回数（ $0$ 回でもよい）行った結果として得られる可能性のある数列 $a$ が何通りあるかを求めて下さい。
（操作）

手順1. $1\le i\le N-1$ を満たす整数 $i$ を選び、$x:=min(a_i,a_{i+1})$ とする。
手順2. $a_i$ と $a_{i+1}$ を $x$ に置き換える。

入力

$N$
$a_1{a}_2\cdots a_N$

$2\le N\le 5000$
$1\le a_i\le N$
$i\ne j$ ならば $a_i\ne a_j$
入力はすべて整数

出力

答えを $998244353$ で割った余りを出力してください。
最後に改行してください。

サンプル

3
3 1 2

4

20
12 16 19 1 17 5 3 18 6 8 14 11 7 10 9 13 15 4 2 20

2708865