← 返回题目列表

AtCoder · tenka1_2018_f

F. 圆形

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给你一系列 N 整数: A_1,A_2,...,A_N.

求排列数 p_1,p_2,...,p_N of 1,2,...,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