B - Chmax Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

(1, 2, \dots, N) の順列 P = (P_1, P_2, \dots, P_N) に対して F(P) を次の手順によって定義します。

  • 数列 B = (1, 2, \dots, N) がある。
    B_i \lt P_{B_i} を満たす整数 i が存在する間、次の操作を行う。
    • B_i \lt P_{B_i} を満たす整数 i のうち最小のものを j とおく。そして、B_j を P_{B_j} に置き換える。
    操作を終了した時点での B を F(P) と定義する。(操作が有限回で終了することは証明できる。)

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。 (1,2,\dots,N) の順列 P であって F(P) = A を満たすものは何個ありますか？答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

F(P) = A を満たす順列 P の個数を 998244353 で割った余りを出力せよ。

入力例 1

4
3 3 3 4

出力例 1

1

例えば P = (2, 3, 1, 4) とする時、 F(P) は以下の手順で (3, 3, 3, 4) に決定します。

  • はじめ、B = (1, 2, 3, 4) である。
  • B_i \lt P_{B_i} を満たす整数 i のうち最小のものは 1 である。B_1 を P_{B_1} = 2 に置き換えて、B = (2, 2, 3, 4) となる。
  • B_i \lt P_{B_i} を満たす整数 i のうち最小のものは 1 である。B_1 を P_{B_1} = 3 に置き換えて、B = (3, 2, 3, 4) となる。
  • B_i \lt P_{B_i} を満たす整数 i のうち最小のものは 2 である。B_2 を P_{B_2} = 3 に置き換えて、B = (3, 3, 3, 4) となる。
  • B_i \lt P_{B_i} を満たす i は存在しないので、操作を終了する。この時点での B = (3, 3, 3, 4) を F(P) として定義する。

F(P) = A を満たす順列 P は (2, 3, 1, 4) の 1 通りのみです。

入力例 2

4
2 2 4 3

出力例 2

0

入力例 3

8
6 6 8 4 5 6 8 8

出力例 3

18

Score: 600 points

Problem Statement

For a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N), we define F(P) by the following procedure:

  • There is a sequence B = (1, 2, \dots, N).
    As long as there is an integer i such that B_i \lt P_{B_i}, perform the following operation:
    • Let j be the smallest integer i that satisfies B_i \lt P_{B_i}. Then, replace B_j with P_{B_j}.
    Define F(P) as the B at the end of this process. (It can be proved that the process terminates after a finite number of steps.)

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N. How many permutations P of (1,2,\dots,N) satisfy F(P) = A? Find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print the number, modulo 998244353, of permutations P that satisfy F(P) = A.

Sample Input 1

4
3 3 3 4

Sample Output 1

1

For example, if P = (2, 3, 1, 4), then F(P) is determined to be (3, 3, 3, 4) by the following steps:

  • Initially, B = (1, 2, 3, 4).
  • The smallest integer i such that B_i \lt P_{B_i} is 1. Replace B_1 with P_{B_1} = 2, making B = (2, 2, 3, 4).
  • The smallest integer i such that B_i \lt P_{B_i} is 1. Replace B_1 with P_{B_1} = 3, making B = (3, 2, 3, 4).
  • The smallest integer i such that B_i \lt P_{B_i} is 2. Replace B_2 with P_{B_2} = 3, making B = (3, 3, 3, 4).
  • There are no more i that satisfy B_i \lt P_{B_i}, so the process ends. The current B = (3, 3, 3, 4) is defined as F(P).

There is only one permutation P such that F(P) = A, which is (2, 3, 1, 4).

Sample Input 2

4
2 2 4 3

Sample Output 2

0

Sample Input 3

8
6 6 8 4 5 6 8 8

Sample Output 3

18