Description

Given a permutation of length $n$, you need to calculate the product of the the minimum divided by the maximum in each non-empty subarray.

Since the answer may be decimal fraction, you only need to output the result after taking the model of $998244353$.

Tips:

1. A permutation of length $n$ is a sequence of integers from $1$ to $n$ of length n containing each number exactly once. For example ,$[1],[4,3,5,1,2] , [3,2,1]$ are permutations, and $[1,1], [0,1],[2,2,1,4]$ are not.

2. An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. For example, the subarrays of $[3,1,2]$ are $[ ],[3],[1],[2],[3,1],[1,2]$ and $[3,1,2]$.

Format

Input

The input has only two lines.

The first line of input is an integer $n(1\le n \le 10^{5})$.

The second line of input is a permutation $P(1\le P[i] \le n)$ of length $n$.

Output

Output one integer indicating the $answer$.

Samples

3
3 1 2

720954255

Hints

The non-empty subarray of $[3,1,2]$ is $[ ],[3],[1],[2],[3,1],[1,2]$ and $[3,1,2]$.

The minimum values are $[3,1,2,1,1,1]$.

The maximum values are $[3,1,2,3,2,3]$.

So the answer is $\frac{3}{3}*\frac{1}{1}*\frac{2}{2}*\frac{1}{3}*\frac{1}{2}*\frac{1}{3}=\frac{1}{18}\equiv 720954255 \pmod{998244353} $.