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)$ 的一个排列。