F - Min-First Search Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N からなる N 頂点の木 T に対して、以下の手順で得られる (1,2,\ldots,N) の順列 P を f(T) とします。

  • はじめ、列 P を空列 () とし、集合 S を \lbrace1\rbrace とする。
  • 以下を N 回繰り返す。
    • S の最小値を x とする。S から x を削除し、P の末尾に xを追加する。
    • その後、T において頂点 x に隣接する頂点を頂点 v _ 1, 頂点 v _ 2,\ldots, 頂点 v _ k とする。i=1,2,\ldots,k について、P に v _ i が含まれていなければ S に v _ i を追加する。

(1,2,\ldots,N) の順列 Q=(Q _ 1,Q _ 2,\ldots,Q _ N) が与えられます。 f(T)=Q となる木 T の個数を 998244353 で割った余りを求めてください。 ただし、ふたつの木は、ある頂点の組 (u,v) が存在して、一方の木では頂点 u と頂点 v の間に辺があり、もう一方の木では辺がないとき、区別されます。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q _ i\le N\ (1\le i\le N)
  • Q _ i\ne Q _ j\ (1\le i\lt j\le N)
  • Q _ 1=1
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
Q _ 1 Q _ 2 \ldots Q _ N

出力

f(T)=Q となる木 T の個数を 998244353 で割った余りを出力せよ。


入力例 1

5
1 3 4 2 5

出力例 1

8

例えば、以下のような木を T とすると、f(T)=Q となります。

f(T) を求める手順は以下の図のように進行します。

この木を含めた以下の図のような 8 つの木が条件を満たします。

よって、8 を出力してください。


入力例 2

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

出力例 2

868586527

条件を満たす木の個数を 998244353 で割った余りを出力してください。


入力例 3

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

出力例 3

910753763

Score : 525 points

Problem Statement

For a tree T with N vertices called vertex 1, vertex 2, \ldots, vertex N, let f(T) be the permutation P of (1,2,\ldots,N) obtained by the following procedure.

  • Initially, let the sequence P be the empty sequence (), and let the set S be \lbrace1\rbrace.
  • Repeat the following N times.
    • Let x be the minimum value of S. Remove x from S, and append x to the end of P.
    • Then, let v_1, v_2, \ldots, v_k be the vertices adjacent to vertex x in T. For i=1,2,\ldots,k, if v _ i is not contained in P, add v _ i to S.

You are given a permutation Q=(Q _ 1,Q _ 2,\ldots,Q _ N) of (1,2,\ldots,N). Find the number, modulo 998244353, of trees T such that f(T)=Q. Here, two trees are distinguished when there exists a pair of vertices (u,v) such that there is an edge between vertex u and vertex v in one tree and there is no edge in the other tree.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q _ i\le N\ (1\le i\le N)
  • Q _ i\ne Q _ j\ (1\le i\lt j\le N)
  • Q _ 1=1
  • All input values are integers.

Input

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

N
Q _ 1 Q _ 2 \ldots Q _ N

Output

Output the number, modulo 998244353, of trees T such that f(T)=Q.


Sample Input 1

5
1 3 4 2 5

Sample Output 1

8

For example, if T is the following tree, then f(T)=Q.

The procedure to find f(T) proceeds as shown in the following figure.

Including this tree, the following eight trees satisfy the condition.

Thus, output 8.


Sample Input 2

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

Sample Output 2

868586527

Output modulo 998244353 the number of trees satisfying the condition.


Sample Input 3

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

Sample Output 3

910753763