M. Modify the Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array which is initially a permutation of $$$n$$$ elements: $$$A=[a_1, a_2, \dots, a_n]$$$.

The array can be modified using the following operation:

  • Let $$$A=[a_1, a_2, \dots, a_k]$$$ be the current array. Select two indices $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq k)$$$, remove the elements $$$a_l, a_{l+1}, \dots a_r$$$ from the array, and insert $$$min(a_l, a_{l+1}, \dots, a_r)$$$ in their place. In other words, the array becomes $$$A=[a_1, a_2, \dots, a_{l-1}, min(a_l, a_{l+1}, \dots, a_r), a_{r+1}, \dots a_k]$$$.

Print the number of different arrays that you can get by performing the given operation any number of times (possibly zero) modulo $$$998244353$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$).

The following line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$). It is guaranteed that $$$[a_1, a_2, \dots, a_n]$$$ forms a permutation of size $$$n$$$.

Output

Print the answer modulo $$$998244353$$$.

Examples
Input
5
1 2 3 4 5
Output
16
Input
5
3 5 2 4 1
Output
9