P12538 [XJTUPC 2025] 泰拉构史

「我相信我们之间的联系会超越时间和空间。」 「就算是海洋沸腾、大气消失，就算我们的卫星接连坠入重力的漩涡，就算我们的太阳凶恶地膨胀，无情地吃掉它的孩子直至万籁俱寂……我们也一样能再见面。」 「在那用黑暗和星点光芒装饰的文明尽头，我们也一样会再见面。一定。」 「我会等到那一天。我肯定会等到那一天。等我。你也要等我。」 「这里万籁俱寂……太安静了。别留下我。」 你是罗德岛的博士，是巴别塔的恶灵，但你更是普瑞赛斯的预言家。文明危在旦夕，但万幸的是，你在一切都来不及之前还是想起了她。去吧，将她自黑暗中找回，不要背叛了在时间中等待的她。 

这是解开谜团的第一步，一道计数题。 有一个长度为 $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$ 取模的结果。

对于第一组样例，初始时的序列为 $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$ 种可能。 由于本题输入输出数据规模较大，建议使用较为快速的输入输出方式。