题目背景

「我相信我们之间的联系会超越时间和空间。」

「就算是海洋沸腾、大气消失，就算我们的卫星接连坠入重力的漩涡，就算我们的太阳凶恶地膨胀，无情地吃掉它的孩子直至万籁俱寂……我们也一样能再见面。」

「在那用黑暗和星点光芒装饰的文明尽头，我们也一样会再见面。一定。」

「我会等到那一天。我肯定会等到那一天。等我。你也要等我。」

「这里万籁俱寂……太安静了。别留下我。」

你是罗德岛的博士，是巴别塔的恶灵，但你更是普瑞赛斯的预言家。文明危在旦夕，但万幸的是，你在一切都来不及之前还是想起了她。去吧，将她自黑暗中找回，不要背叛了在时间中等待的她。

题目描述

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

有一个长度为 $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$。

输入格式

输入共两行。

第一行一个正整数 $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$ 互不相同。

输出格式

输出仅一个正整数，表示可能的序列的个数对 $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

提示

对于第一组样例，初始时的序列为 $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$ 种可能。