AT_utpc2020_e.Sort Segments

Enjapma くん有一个 $ (1,\ 2,\ \ldots,\ N) $ 的排列 $ P = (P_1,\ P_2,\ \ldots,\ P_N) $。

Enjapma くん将恰好进行 $ 1 $ 次如下操作：

• 选择一个整数 $ k $（$ k \geq 0 $），以及满足 $ 1 \leq l_1 < r_1 < l_2 < r_2 < \cdots < l_k < r_k \leq N $ 的整数序列 $ (l_1, r_1, l_2, r_2, \ldots, l_k, r_k) $，然后对于每个 $ i $（$ 1 \leq i \leq k $），将 $ P_{l_i}, P_{l_i+1}, \ldots, P_{r_i} $ 按升序排列。

请你求出，经过一次操作后，可能得到的不同排列的个数，答案对 $ 998244353 $ 取模。

输入为如下格式：

$ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

输出一个整数，表示答案。

限制

• 输入均为整数。
• $ 1 \leq N \leq 2 \times 10^5 $
• $ 1 \leq P_i \leq N $
• $ P_1, P_2, \ldots, P_N $ 互不相同。

部分分

• 若能正确解决 $ 1 \leq N \leq 3000 $ 的数据，将获得 $ 50 $ 分。

样例说明 1

• 取 $ k = 0 $ 时，$ P = (3, 2, 4, 1) $。
• 取 $ k = 1 $，选择 $ (l_1, r_1) = (1, 2) $，$ P = (2, 3, 4, 1) $。
• 取 $ k = 1 $，选择 $ (l_1, r_1) = (1, 4) $，$ P = (1, 2, 3, 4) $。
• 取 $ k = 1 $，选择 $ (l_1, r_1) = (2, 4) $，$ P = (3, 1, 2, 4) $。
• 取 $ k = 1 $，选择 $ (l_1, r_1) = (3, 4) $，$ P = (3, 2, 1, 4) $。
• 取 $ k = 2 $，选择 $ (l_1, r_1, l_2, r_2) = (1, 2, 3, 4) $，$ P = (2, 3, 1, 4) $。

除此之外，其他操作方式得到的结果都与上述 $ 6 $ 种情况重复。

由 ChatGPT 4.1 翻译