Description

You are given a sequence $a$ and two operations:

1. Choose $a_i < a_{i+1}$ and delete $a_{i+1}$.
2. Choose $a_i < a_{i+1}$ and swap these two numbers.

You must repeatedly perform these operations until no more operations can be done. How many distinct sequences can be obtained at the end?

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th integer is $a_i$.

Output Format

Output an integer representing the number of distinct sequences obtained at the end, modulo $998244353$.

5
4 5 2 3 1

4

4
2 2 2 2

1

Hint

Sample Explanation

For Sample #1, there are four possible outcomes:

• $[4, 2, 1]$: Obtained by performing two deletions to remove $5$ and $3$.
• $[5, 4, 2, 1]$: Obtained by deleting $3$ and moving $5$ to the front.
• $[5, 4, 3, 2, 1]$: Obtained by performing two swaps to sort the sequence.
• $[4, 3, 2, 1]$: Obtained by deleting $5$ and then sorting the sequence.

For Sample #2, no operations can be performed initially.

Constraints

For all test cases, $1 \le n \le 10^5$, $1 \le a_i \le 10^9$.

Generated by Deepseek V3.