T501030 「FSLOI Round I」Mountain

**[Chinese statement.](https://www.luogu.com.cn/problem/T471106?contestId=163361) You must submit your code at the Chinese version of the statement.** Mountains are wineglasses discarded by the Creator.

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

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 a single integer, representing the answer modulo $998{,}244{,}353$.

**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$ |Subtask Id|Score|Special Property| |:-----:|:-----:|:-----:| |$1$|$10$|$n \leq 18$| |$2$|$15$|$n \leq 80$| |$3$|$15$|$A$| |$4$|$20$|$B$| |$5$|$40$|-| Special Property $A$: $a$ is a **peak**. Special Property $B$: $a_1,a_2,\dots,a_n$ are pairwise distinct.