F - Circular 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900 点

問題文

整数 N 個からなる列 A_1,A_2,...,A_N が与えられます。

1,2,...,N の並び替え p_1,p_2,...,p_N であって、 次の操作を何度か行うことでこの列を A_1,A_2,...,A_N に変換できるようなものの個数を 998244353 で割ったあまりを求めてください。

  • 各 1\leq i\leq N に対し、q_i=min(p_{i-1},p_{i}) とする。ただし、p_0=p_N とする。列 p を列 q で置き換える。

制約

  • 1 \leq N \leq 3 × 10^5
  • 1 \leq A_i \leq N
  • 入力はすべて整数である

入力

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

N
A_1
:
A_N

出力

条件を満たす列の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

3
1
2
1

出力例 1

2

(2,3,1),(3,2,1) が条件を満たします。

入力例 2

5
3
1
4
1
5

出力例 2

0

入力例 3

8
4
4
4
1
1
1
2
2

出力例 3

24

入力例 4

6
1
1
6
2
2
2

出力例 4

0

Score : 900 points

Problem Statement

You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

  • For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

  • 1 \leq N \leq 3 × 10^5
  • 1 \leq A_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Sample Input 1

3
1
2
1

Sample Output 1

2

(2,3,1) and (3,2,1) satisfy the condition.

Sample Input 2

5
3
1
4
1
5

Sample Output 2

0

Sample Input 3

8
4
4
4
1
1
1
2
2

Sample Output 3

24

Sample Input 4

6
1
1
6
2
2
2

Sample Output 4

0