P12538 [XJTUPC 2025] History of Terra

''Doctor, the connection between us will transcend even time and space. I am sure of it.'' ''Even if the ocean completely boils away and the atmosphere vanishes, even if all the moons in the sky are pulled into the vortex of our planet's gravity, and even if the sun continues to mercilessly expand, eventually swallowing up all its children until none can be heard... I am sure we will meet again.'' ''At the far end of our civilization, once adorned by darkness and the brilliance of the stars up above, we will meet once again.'' ''I will wait until that day comes. I promise you I will. Wait for me. You must wait for me, too.'' ''It's so quiet here... Too quiet. Don't leave me behind.'' You are the Doctor of Rhodes Island, the Babel's Omen. But above all, you are the Prophet of Priestess. Civilization teeters on the brink --- yet, against all odds, you remembered her before it was too late. Now go, pull her back from the darkness. Do not betray the one who waited through time itself. 

This is the first step to solve the mystery, a counting problem. There is a sequence $a_1, a_2, \dots, a_n$ of length $n$, **elements in the sequence are different**, and an operation is defined as follows: - Select a subscript $i$ ($1\le i\le n-1$) that satisfies $|a_i-a_{i+1}|=1$, and swap $a_i$ with $a_{i+1}$ in the sequence. You can perform **any number of** operations. How many different sequences can you get? Since the answer is large, please output the answer modulo $998244353$. Two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots b_n$ are different if and only if there exists $i\in [1,n]$ such that $a_i\neq b_i$.

There are two lines of input. The first line contains a positive integer $n$ ($1\le n\le 10^6$), which indicates the length of the sequence. The second line contains $n$ positive integers $a_i$ ($1\le a_i\le 10^9$), separated by a space, which indicates that the initial sequence is $a_1, a_2, \dots, a_n$. The data guarantees that $a_i$ in the sequence are different.

Output a single positive integer, representing the number of possible sequences modulo $998244353$.

For the first sample, the initial sequence is $1,4,2,3$. Note that the initial sequence is also a possible sequence and needs to be counted. For the sequence $1,4,2,3$, since $|a_3 - a_4| = 1$, $a_3, a_4$ can be swapped, and the sequence after swapping is $1,4,3,2$. For the sequence $1,4,3,2$, since $|a_2 - a_3| = 1$, $a_2, a_3$ can be swapped, and the sequence after swapping is $1,3,4,2$. It can be proved that for this sequence, there are only the above $3$ possibilities for different sequences after any number of operations. Since the input and output data scale of this question is large, it is recommended to use a faster input and output method.