AT_abc439_f [ABC439F] Beautiful Kadomatsu

A sequence $ a=(a_1,a_2,\dots,a_k) $ of length $ k $ is defined to be **kadomatsu-like** as follows: - Let $ x $ be the number of integers $ i $ that satisfy $ 2 \le i \le k-1 $ , $ a_{i-1} < a_i $ , and $ a_i > a_{i+1} $ . - Let $ y $ be the number of integers $ i $ that satisfy $ 2 \le i \le k-1 $ , $ a_{i-1} > a_i $ , and $ a_i < a_{i+1} $ . - The sequence $ a $ is called **kadomatsu-like** if and only if $ x > y $ . You are given a permutation $ P $ of $ (1,2,\dots,N) $ . Find the number, modulo $ 998244353 $ , of (not necessarily contiguous) subsequences of $ P $ that are kadomatsu-like.

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

Output the answer.

### Sample Explanation 1 Among the subsequences of $ P $ , the following four are kadomatsu-like: - $ (1,3,4,2) $ - $ (1,3,2) $ - $ (1,4,2) $ - $ (3,4,2) $ ### Sample Explanation 3 For example, the subsequence $ a=(10,13,12,5,7,9,20,3) $ is kadomatsu-like. - We have $ a_{i-1} < a_i $ and $ a_i > a_{i+1} $ for $ i=2,7 $ , so $ x=2 $ . - We have $ a_{i-1} > a_i $ and $ a_i < a_{i+1} $ for $ i=4 $ , so $ y=1 $ . - Since $ x > y $ , the subsequence $ a $ is kadomatsu-like. ### Constraints - All input values are integers. - $ 1 \le N \le 3 \times 10^5 $ - $ P $ is a permutation of $ (1,2,\dots,N) $ .