分数: 525 点
问题陈述
一个序列 a=(a_1,a_2,\dots,a_k) 长度 k 定义为 门松式 如下:
- 让 x 是整数的个数 i 满足 2 \le i \le k-1, a_{i-1} < a_i,和 a_i > a_{i+1}.
- 让 y 是整数的个数 i 满足 2 \le i \le k-1, a_{i-1} > a_i,和 a_i < a_{i+1}.
- 序列 a 被称为 门松式 当且仅当 x > y.
给你一个排列 P of (1,2,\dots,N).
求模数 998244353,(不一定是连续的)子序列 P 是门松式的。
约束
- 所有输入值均为整数。
- 1 \le N \le 3 \times 10^5
- P 是一个排列 (1,2,\dots,N).
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \dots P_N
输出
输出答案。
示例输入 1
4 1 3 4 2
示例输出 1
4
的子序列中 P,以下四个是类似门松的:
- (1,3,4,2)
- (1,3,2)
- (1,4,2)
- (3,4,2)
示例输入 2
1 1
示例输出 2
0
示例输入 3
20 11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3
示例输出 3
431610
例如,子序列 a=(10,13,12,5,7,9,20,3) 类似于门松。
- 我们有 a_{i-1} < a_i 和 a_i > a_{i+1} 为 i=2,7,所以 x=2.
- 我们有 a_{i-1} > a_i 和 a_i < a_{i+1} 为 i=4,所以 y=1.
- 自从 x > y,子序列 a 类似于门松。