← 返回题目列表

AtCoder · agc058_b

B. 相邻 Chmax

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

分数: 700 点

问题陈述

给你一个排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

您可以执行以下操作零次或多次。

  • 选择一个整数 i (1 \leq i \leq N-1)。 让 v=\max(P_i,P_{i+1}) 并替换以下值 P_i 和 P_{i+1} 与 v.

有多少个序列 P 你手术后可以吗?求计数模数 998244353.

约束

  • 2 \leq N \leq 5000
  • (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
  • 输入中的所有值都是整数。

输入

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

N
P_1 P_2 \cdots P_N

输出

打印答案。


示例输入 1

3
1 3 2

示例输出 1

4

四个序列 P 可以成为 (1,3,2), (3,3,2), (1,3,3),和 (3,3,3).


示例输入 2

4
2 1 3 4

示例输出 2

11

示例输入 3

10
4 9 6 3 8 10 1 2 7 5

示例输出 3

855