AT_abc439_f [ABC439F] Beautiful Kadomatsu

一个长度为 $ k $ 的序列 $ a = (a_1, a_2, \ldots, a_k) $ 被定义为**门松型**的，定义如下： - 令 $ x $ 为满足 $ 2 \leq i \leq k - 1, a_{i-1} < a_i $ 且 $ a_i > a_{i+1} $ 的整数 $ i $ 的个数。 - 令 $ y $ 为满足 $ 2 \leq i \leq k - 1, a_{i-1} > a_i $ 且 $ a_i < a_{i+1} $ 的整数 $ i $ 的个数。 - 序列 $ a $ 被称为**门松型**的，当且仅当 $ x > y $。 给你一个 $(1, 2, \ldots, N)$ 的排列 $ P $。 求 $ P $ 中门松型的（不一定连续的）子序列的数量，结果对 $998244353$ 取模。

输入通过标准输入按以下格式给出： > $N \\ P_1 \ P_2 \cdots \ P_N \\$

输出答案（对 $998244353$ 取模）。

## 样例解释1 在 $P$ 的子序列中，以下四个是“门松型”的： - $(1, 3, 4, 2)$ - $(1, 3, 2)$ - $(1, 4, 2)$ - $(3, 4, 2)$ ## 样例解释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$ 是“门松型”的。 ## 限制 - 所有输入值均为整数。 - $ 1 \leq N \leq 3 \times 10^5 $ - $ P $ 是 $(1, 2, \ldots, N)$ 的一个排列。