A Little Bit of Cryptography Never Hurt Anybody

Recently, Professor L. developed a special cipher that no one could break. Anton took this personally and decided to crack it by himself. He noticed that before every message there was a small pyramid drawn and a permutation $p$ of $n$ elements.

After some brainstorming, he understood that every message had a different cipher based on the number of different permutations of $n$ elements that were both:

• pyramidal permutations.

• lexicographically smaller than $p$.

Your task is for a given $p$ to find out how many pyramidal permutations exist that are lexicographically smaller than $p$. As this number may be too large, output it by modulo $998244353$.

A permutation of $n$ elements is called pyramidal if there exists an index $k$ $(1\le k\le n)$, such that:

• for each $i$ ($1<i\le k$), $p_{i-1}<p_i$;

• for each $i$ ($k<i\le n$), $p_{i-1}>p_i$.

A sequence of integers $a_1,a_2,\dots ,a_n$ is called a permutation if the sequence contains each integer from $1$ to $n$ exactly once. For example, $[1,5,3,4,2]$ is a permutation. However, $[1,3,4]$ is not (it doesn't contain $2$ and contains $4$, which should not appear in the sequence) and $[1,2,2,3]$ is not as well (it contains $2$ twice and doesn't contain $4$).

An array $a$ is lexicographically smaller than an array $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a\ne b$;

• in the first position where a and b differ, the array $a$ has a smaller element than array $b$.

Input

The first line contains a single integer $n$ $(1\le n\le 10^6)$ — the length of the permutation.

The second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — elements of the permutations.

It is guaranteed that $p$ is a permutation.

Output

Output a single integer — answer for the task.

Examples

Note

In the first example, there are $7$ pyramidal permutations less or equal to $p$:

1. $[1,2,3,4,5]\le [1,5,3,4,2]$

2. $[1,2,3,5,4]\le [1,5,3,4,2]$

3. $[1,2,4,5,3]\le [1,5,3,4,2]$

4. $[1,2,5,4,3]\le [1,5,3,4,2]$

5. $[1,3,4,5,2]\le [1,5,3,4,2]$

6. $[1,3,5,4,2]\le [1,5,3,4,2]$

7. $[1,4,5,3,2]\le [1,5,3,4,2]$

Note that $[1,5,4,3,2]>[1,5,3,4,2]$.

In the second example, there is only $1$ pyramidal permutation less or equal to $p$:

1. $[1,2,3]\le [1,2,3]$

Scoring

1. ($8$ points): $n\le 10$;

2. ($7$ points): $n\le 30$;

3. ($6$ points): $n\le 60$;

4. ($11$ points): $n\le 500$;

5. ($13$ points): $n\le 10000$;

6. ($22$ points): $n\le 10^5$;

7. ($33$ points): no additional restrictions.