AT_abc439_f [ABC439F] Beautiful Kadomatsu

長さ $ k $ の数列 $ a=(a_1,a_2,\dots,a_k) $ が **門松的** であることを、以下のようにして定めます。 - $ 2 \le i \le k-1 $ かつ $ a_{i-1} < a_i $ かつ $ a_i > a_{i+1} $ を満たす整数 $ i $ の個数を $ x $ とする。 - $ 2 \le i \le k-1 $ かつ $ a_{i-1} > a_i $ かつ $ a_i < a_{i+1} $ を満たす整数 $ i $ の個数を $ y $ とする。 - $ x > y $ であるとき、またそのときに限り、数列 $ a $ を **門松的** であると言います。 $ (1,2,\dots,N) $ の順列 $ P $ が与えられます。 $ P $ の (連続でなくともよい) 部分列であって、門松的であるものの個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

答えを出力せよ。

### Sample Explanation 1 $ P $ の部分列のうち、門松的であるものは以下の $ 4 $ つです。 - $ (1,3,4,2) $ - $ (1,3,2) $ - $ (1,4,2) $ - $ (3,4,2) $ ### Sample Explanation 3 例えば、部分列 $ a=(10,13,12,5,7,9,20,3) $ は門松的です。 - $ i=2,7 $ に対して $ a_{i-1} < a_i $ かつ $ a_i > a_{i+1} $ が成り立つので、 $ x=2 $ です。 - $ i=4 $ に対して $ a_{i-1} > a_i $ かつ $ a_i < a_{i+1} $ が成り立つので、 $ y=1 $ です。 - $ x > y $ であるので、部分列 $ a $ は門松的です。 ### Constraints - 入力は全て整数 - $ 1 \le N \le 3 \times 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列