← 返回题目列表

AtCoder · arc171_b

B. 取最大值

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

分数: 600 点

问题陈述

对于排列 P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N),我们定义 F(P) 通过以下程序:

  • 有一个序列 B = (1, 2, \dots, N).
    只要有一个整数 i 这样 B_i \lt P_{B_i},执行以下操作:
    • 让 j 是最小的整数 i 满足 B_i \lt P_{B_i}。然后,更换 B_j 与 P_{B_j}.
    定义 F(P) 作为 B 在此过程结束时。 (可以证明,该过程在有限步数后终止。)

给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N。有多少种排列 P of (1,2,\dots,N) 满足 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

输出

打印数字,模数 998244353,排列 P 满足 F(P) = A.


示例输入 1

4
3 3 3 4

示例输出 1

1

例如,如果 P = (2, 3, 1, 4),那么 F(P) 确定为 (3, 3, 3, 4) 通过以下步骤:

  • 最初, B = (1, 2, 3, 4).
  • 最小整数 i 这样 B_i \lt P_{B_i} is 1。更换 B_1 与 P_{B_1} = 2, 制作 B = (2, 2, 3, 4).
  • 最小整数 i 这样 B_i \lt P_{B_i} is 1。更换 B_1 与 P_{B_1} = 3, 制作 B = (3, 2, 3, 4).
  • 最小整数 i 这样 B_i \lt P_{B_i} is 2。更换 B_2 与 P_{B_2} = 3, 制作 B = (3, 3, 3, 4).
  • 没有更多了 i 满足 B_i \lt P_{B_i},因此该过程结束。目前的 B = (3, 3, 3, 4) 定义为 F(P).

只有一种排列 P 这样 F(P) = A,即 (2, 3, 1, 4).


示例输入 2

4
2 2 4 3

示例输出 2

0

示例输入 3

8
6 6 8 4 5 6 8 8

示例输出 3

18