Problem Description

Yana, Mino, White, and Huzz are best friends.

Having finally finished the coach’s demanding tasks, Huzz had earned a rest. He found it on $1$ lazy afternoon, where the world seemed to slow to a crawl, wrapped in the warm, golden haze of impending dusk. A gentle breeze did little more than stir the dust motes dancing in the sunbeams slanting through the leaves of a great oak tree.

In that sleepy, comfortable void, Huzz found a permutation in his soft shark toy. He decided to share it with his friends for fun.

Mino loves splitting. He can split this permutation into several contiguous segments.

Yana loves swapping. He can choose $1$ contiguous segment and swap its maximum and minimum elements.

Specifically, they can perform the following $2$ types of operations any number of times, in any order:

• split: Choose $1$ contiguous segment whose length is greater than $1$. Then choose $1$ position inside it and split it into $2$ adjacent contiguous segments. For example, $(a_i, \ldots, a_j)$ can be split into $(a_i, \ldots, a_k)$ and $(a_{k+1}, \ldots, a_j)$, where $i \le k < j$.
• swap: Choose $1$ contiguous segment and swap its maximum and minimum elements.

After performing any number of operations, they stop performing, and all resulting segments are merged in their original order to form a new permutation.

White loves counting. She wonders — how many distinct permutations can they obtain?

As the result can be very large, you only need to find the answer modulo $998\,244\,353$.

Input Format

The first line the input contains an integer $n$ ($1 \le n \le 500$), the length of the permutation.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), representing the permutation itself. It’s guaranteed that $\{a_n\}$ is a permutation.

Output Format

Print an integer, the number of distinct permutations they can obtain modulo $998\,244\,353$.

4
1 4 2 3

10

7
5 1 4 2 6 3 7

340

Hint

In the first sample, the following are all possible permutations they can obtain:

$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$