Description

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$.

Input Format

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 Format

Output a single positive integer, representing the number of possible sequences modulo $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

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.