AT_awtf2026algo_b Window Records

長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます． 以下の条件をすべて満たす長さ $ N $ の正整数列 $ x=(x_1,x_2,\ldots,x_N) $ の個数を $ 998244353 $ で割った余りを求めてください． - すべての $ i $ に対し $ x_i \leq A_i $ が成り立つ． - ある $ (1,2,\ldots,2N-1) $ の順列 $ p=(p_1,p_2,\ldots,p_{2N-1}) $ が存在し，以下の条件を満たす． - 各 $ i $ ( $ 1 \leq i \leq N $ ) に対し，長さ $ N $ の数列 $ (p_i,p_{i+1},\ldots,p_{i+N-1}) $ を考える．この列の prefix max の種類数がちょうど $ x_i $ である．より正確に言えば， $ p_j = \max_{i \leq k \leq j} p_k $ となる $ j $ ( $ i \leq j \leq i+N-1 $ ) の個数が $ x_i $ である．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ．

### Sample Explanation 1 例えば $ x=(2,1) $ について考えると， $ p=(2,3,1) $ によって条件が満たされます． $ x $ としてあり得るのは， $ (1,1),(1,2),(2,1),(2,2) $ の $ 4 $ 通りです． ### Sample Explanation 3 例えば $ x=(3,1,3) $ について考えると，どんな $ p $ を選んでも条件を満たしません． ### Constraints - $ 2 \leq N \leq 50 $ - $ 1 \leq A_i \leq N $ - 入力はすべて整数