Gats Between the Lookouts

Time limit: 3000 msMemory limit: 256 MB

Gats has found $N$ platforms arranged in a line and numbered $1,2,\ldots,N$ from left to right. Platform $i$ has height $H_i$ , and one fish is waiting there.

Gats visits every platform exactly once. His visiting order is chosen uniformly at random from all $N!$ possible orders.

When Gats visits platform $i$ , consider only platforms visited earlier:

If there is a previously visited platform to the left, let $L$ be the greatest previously visited index satisfying $L<i$ .
If there is a previously visited platform to the right, let $R$ be the least previously visited index satisfying $i<R$ .

Gats catches the fish at platform $i$ if both $L$ and $R$ exist and

\min(H_L,H_R)<H_i<\max(H_L,H_R).

Otherwise, that landing catches no fish. Each platform is visited only once, so each fish can be caught at most once.

Find the expected total number of fish Gats catches.

Input

The first line contains an integer $N$ ( $3 \le N \le 2000$ ), the number of platforms.

The second line contains $N$ integers $H_1,H_2,\ldots,H_N$ (), where is the height of platform . Heights are not necessarily distinct.

Output

Print one integer: the expected number of fish caught, modulo $M=998244353$ .

Formally, if the expectation is represented as $p/q$ , where $q$ is not divisible by $M$ , print

p \cdot q^{- 1}

Samples

Sample 1

Input

3
1 2 3

Output

332748118

The expected number of fish caught is $1/3$ , whose required residue is $332748118$ .

Sample 2

Input

5
2 5 3 1 4

Output

765320671

For these platform heights, the expected number of fish caught is $11/30$ .

Gats Between the Lookouts

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions