E - Drop Min Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

(1,2,\ldots,N) の順列 P と、空の配列 A があります。 P に対して以下の操作を N-1 回行います。

  • 隣接する 2 要素を選ぶ。選んだうち小さい方の要素を P から削除し、削除した要素の前後を結合する。削除した要素を A の末尾に追加する。

最終的にできる長さ N-1 の数列 A としてあり得るものの数を 998244353 で割ったあまりを求めてください。

制約

  • 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

最終的な A としては (1,2,3) の順列 6 通りの全てがあり得ます。

例えば、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

Score : 700 points

Problem Statement

There is a permutation P of (1,2,\ldots,N) and an empty array A. Perform the following operation N-1 times on P:

  • Choose two adjacent elements. Remove the smaller of the chosen elements from P and concatenate the parts before and after the removed element. Append the removed element to the end of A.

Find the number, modulo 998244353, of possible final sequences A of length N-1.

Constraints

  • 2 \le N \le 2\times 10^5
  • 1 \le P_i \le N
  • P is a permutation of (1,2,\ldots,N).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

4
1 2 3 4

Sample Output 1

6

All six permutations of (1,2,3) are possible as the final A.

For example, A=(2,1,3) can be obtained as follows:

  • Choose 2,3. Remove 2, and now P=(1,3,4), A=(2).
  • Choose 1,3. Remove 1, and now P=(3,4), A=(2,1).
  • Choose 3,4. Remove 3, and now P=(4), A=(2,1,3).

Sample Input 2

3
3 1 2

Sample Output 2

1

Sample Input 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

Sample Output 3

303178128