B - Adjacent Chmax Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます．

あなたは，以下の操作を 0 回以上行うことができます．

  • 整数 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) の 4 通りです．

入力例 2

4
2 1 3 4

出力例 2

11

入力例 3

10
4 9 6 3 8 10 1 2 7 5

出力例 3

855

Score : 700 points

Problem Statement

You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

You may perform the following operation zero or more times.

  • Choose an integer i (1 \leq i \leq N-1). Let v=\max(P_i,P_{i+1}) and replace the values of P_i and P_{i+1} with v.

How many sequences are there that P can be after your operations? Find the count modulo 998244353.

Constraints

  • 2 \leq N \leq 5000
  • (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N

Output

Print the answer.

Sample Input 1

3
1 3 2

Sample Output 1

4

The four sequences that P can become are (1,3,2), (3,3,2), (1,3,3), and (3,3,3).

Sample Input 2

4
2 1 3 4

Sample Output 2

11

Sample Input 3

10
4 9 6 3 8 10 1 2 7 5

Sample Output 3

855