Problem Description

Enjapma has a permutation \( P = (P_1, P_2, \ldots, P_N) \) of the sequence \( (1, 2, \ldots, N) \).

Enjapma will perform the following operation exactly once:

• Choose an integer \( k (\geq 0) \) and a sequence of integers \( (l_1, r_1, l_2, r_2, \ldots, l_k, r_k) \) satisfying \( 1 \leq l_1 < r_1 < l_2 < r_2 < \cdots < l_k < r_k \leq N \). Then, for each \( i (1 \leq i \leq k) \), rearrange \( P_{l_i}, P_{l_i+1}, \ldots, P_{r_i} \) in ascending order.

Find the number of possible permutations of \( P \) after the operation, modulo \( 998244353 \).

Input Format

The input is given in the following format:

\( N \) \( P_1 \) \( P_2 \) \( \ldots \) \( P_N \)

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

4
3 2 4 1

Sample Output #1

6

Sample Input #2

12
4 1 9 5 3 8 7 10 6 2 12 11

Sample Output #2

300

Notes/Hints

Constraints

• All inputs are integers.
• \( 1 \leq N \leq 2 \times 10^5 \)
• \( 1 \leq P_i \leq N \)
• \( P_1, P_2, \ldots, P_N \) are all distinct.

Partial Points

• If you solve the dataset satisfying \( 1 \leq N \leq 3000 \), you will be awarded 50 points.

Sample Explanation 1

• If \( k = 0 \), \( P = (3, 2, 4, 1) \).
• If \( k = 1 \) and \( (l_1, r_1) = (1, 2) \), \( P = (2, 3, 4, 1) \).
• If \( k = 1 \) and \( (l_1, r_1) = (1, 4) \), \( P = (1, 2, 3, 4) \).
• If \( k = 1 \) and \( (l_1, r_1) = (2, 4) \), \( P = (3, 1, 2, 4) \).
• If \( k = 1 \) and \( (l_1, r_1) = (3, 4) \), \( P = (3, 2, 1, 4) \).
• If \( k = 2 \) and \( (l_1, r_1, l_2, r_2) = (1, 2, 3, 4) \), \( P = (2, 3, 1, 4) \).

There are other ways to perform the operation, but the results will overlap with one of the above 6 cases.

见题面 Input 部分

见题面 Output 部分