← 返回题目列表

AtCoder · abc439_f

I. 美丽的门松

中文机器翻译题面 查看原题

分数: 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 类似于门松。