← 返回题目列表

AtCoder · arc212_e

E. 下降最小值

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

分数: 700 点

问题陈述

有一个排列 P of (1,2,\ldots,N) 和一个空数组 A。 执行以下操作 N-1 次 P:

  • 选择两个相邻元素。从中删除所选元素中较小的一个 P 并连接被删除元素之前和之后的部分。将删除的元素添加到末尾 A.

求模数 998244353,可能的最终序列 A 长度 N-1.

约束

  • 2 \le N \le 2\times 10^5
  • 1 \le P_i \le N
  • P 是一个排列 (1,2,\ldots,N).
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

输出答案。


示例输入 1

4
1 2 3 4

示例输出 1

6

的所有六种排列 (1,2,3) 有可能作为最终 A.

例如, A=(2,1,3) 可以通过如下方式获得:

  • 选择 2,3。删除 2,现在 P=(1,3,4), A=(2).
  • 选择 1,3。删除 1,现在 P=(3,4), A=(2,1).
  • 选择 3,4。删除 3,现在 P=(4), A=(2,1,3).

示例输入 2

3
3 1 2

示例输出 2

1

示例输入 3

24
10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11

示例输出 3

303178128