Chmax

时间限制：2s
空间限制：1024MB

题目描述

对 $1$ 到 $N$ 的排列 $P$ 定义 $F(P)$：初始令 $B=(1,2,\ldots,N)$；只要存在 $i$ 满足 $B_i<P_{B_i}$，就取最小的这种 $i$，把 $B_i$ 替换为 $P_{B_i}$。过程结束时的 $B$ 即为 $F(P)$。

给定长度为 $N$ 的序列 $A$，求满足 $F(P)=A$ 的排列 $P$ 的数量，对 $998244353$ 取模。

输入格式

第一行输入整数 $N$。第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出答案对 $998244353$ 取模后的值。

样例输入 1

4
3 3 3 4

样例输出 1

1

样例输入 2

4
2 2 4 3

样例输出 2

0

样例输入 3

8
6 6 8 4 5 6 8 8

样例输出 3

18

数据范围

对于所有数据，$1\le N\le2\times10^5$，$1\le A_i\le N$。