Description

这是解开谜团的第一步，一道计数题。

有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，序列中的元素互不相同，一次操作定义如下：

• 选择一个下标 $i$ ($1\le i\le n-1$) 满足 $|a_i-a_{i+1}|=1$，在序列中交换 $a_i$ 与 $a_{i+1}$。

你可以进行 任意次 操作。你能得到多少种不同的序列？由于答案较大，请输出答案对 $998244353$ 取模的结果。

两个序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots b_n$ 不同当且仅当存在 $i\in [1,n]$ 使得 $a_i\neq b_i$。

Input Format

输入共两行。

第一行一个正整数 $n$ ($1\le n\le 10^6$) ，表示序列的长度。

第二行 $n$ 个正整数 $a_i$ ($1\le a_i\le 10^9$)，用一个空格分隔，表示初始的序列为 $a_1, a_2, \dots, a_n$。数据保证序列中的 $a_i$ 互不相同。

Output Format

输出仅一个正整数，表示可能的序列的个数对 $998244353$ 取模的结果。

4
1 4 2 3

3

9
11 4 5 14 19 1 9 8 10

6

1
1

1

12
4 3 7 6 8 11 9 10 12 14 13 15

90

Hint

对于第一组样例，初始时的序列为 $1,4,2,3$。注意，初始时的序列也是一种可能的序列，需要计数。

对序列 $1,4,2,3$，因为 $|a_3 - a_4| = 1$，此时可以交换 $a_3, a_4$，交换后序列为 $1,4,3,2$。

对序列 $1,4,3,2$，因为 $|a_2 - a_3| = 1$，此时可以交换 $a_2, a_3$，交换后序列为 $1,3,4,2$。

可以证明，对于该序列，经过任意次操作不同的序列只有上述 $3$ 种可能。

由于本题输入输出数据规模较大，建议使用较为快速的输入输出方式。