Description

An integer sequence $a$ of length $m(m \ge 3)$ is called a peak if and only if it satisfies the following condition:

• There exists an integer $x(2 \le x \le m-1)$ where $a_1<a_2<\dots<a_x>a_{x+1}>\dots>a_m$. We call $a_x$ as the height of the peak.

An integer sequence $b$ is called a mountain if and only if it satisfies one of the following conditions:

• $b$ is a peak.

• $b$ can be split into at least two continuous subsequences, where each subsequence is a peak and the heights of the peaks are strictly increasing from left to right.

For example, the sequence $\{2,4,3,1,5,2,1\}$ is a mountain, because it can be split into two peaks: $\{2,4,3\}$ and $\{1,5,2,1\}$, and the heights of the peaks $(\{4,5\})$ are strictly increasing. $\{2,4,3,5,2,1\}$ is not a peak because it itself isn't a peak and it cannot be split into multiple peaks.

You are given a sequence $a$ of length $n$. You need to find out the number of mountains among all the subsequences of $a$.

The answer may be very large, so please print the answer modulo $998{,}244{,}353$.

Note that, for two subsequences $s=\{a_{i_1},a_{i_2},\dots,a_{i_p}\}$ and $t=\{a_{j_1},a_{j_2},\dots,a_{j_q}\}$, they are different if and only if $\{i_1,i_2,\dots,i_p\}\neq\{j_1,j_2,\dots,j_q\}$. In other words, even if two subsequences have the same elements, they are distinguished as long as the positions of the elements are different.

Input Format

The first line of the input contains a single integer $n$ representing the length of the given sequence.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$, representing the sequence $a$.

Output Format

Output a single integer, representing the answer modulo $998{,}244{,}353$.

4
1 2 2 1

2

7
2 4 3 1 5 2 1

35

20
2 3 5 6 8 7 6 5 6 7 8 8 8 8 4 3 5 6 7 4

15085

Hint

Example Explanation

In the first example, $\{a_1,a_2,a_4\}$ and $\{a_1,a_3,a_4\}$ are mountains.

Constraints

Subtasks are used in this problem.

For all tests, it is guaranteed that:

• $1 \leq n \leq 500$
• $1 \leq a_i \leq 10^6$

Special Property $A$: $a$ is a peak.

Special Property $B$: $a_1,a_2,\dots,a_n$ are pairwise distinct.