Problem Description

There is an open space with $n$ mountains, each with a height value $h$. Xiao Z is on the tallest mountain and wants to travel to the shortest one.

He has the following movement options:

1. Move to a mountain that is lower than the current one.
2. Move to a mountain of the same height as the current one (cannot stay on the current mountain), but this option can only be executed once for each height (i.e., cannot consecutively move to the same height three or more times).

Each move consumes stamina, which is equal to the horizontal distance between the two mountains (if moving from the $i$-th mountain to the $j$-th mountain, the stamina consumed is $|i-j|$).

If there are multiple options for a move, Xiao Z will choose any one with equal probability. Calculate the expected value of the stamina consumed, modulo $998,244,353$.

Input Format

The first line contains a positive integer $n$, representing the number of mountains.
The next line contains $n$ positive integers, representing the heights of each mountain.

Output Format

An integer representing the final answer modulo $998,244,353$.

Sample Input and Output

Sample Input #1

4
1 3 3 7

Sample Output #1

332748121

Sample Input #2

3
1 3 2

Sample Output #2

2

Sample Input #3

10
1 2 2 2 4 3 2 6 5 9

Sample Output #3

384244861

Notes

Sample 1 Explanation

The value before modulo is $\frac{10}{3}$.

The possible paths (with mountain numbers) are:

1. $(4,1)$ with probability $\frac{1}{3}$, consuming $3$ stamina.
2. $(4,3,1)$ with probability $\frac{1}{3} \times \frac{1}{2}$, consuming $3$ stamina.
3. $(4,2,1)$ with probability $\frac{1}{3} \times \frac{1}{2}$, consuming $3$ stamina.
4. $(4,3,2,1)$ with probability $\frac{1}{3} \times \frac{1}{2}$, consuming $3$ stamina.
5. $(4,2,3,1)$ with probability $\frac{1}{3} \times \frac{1}{2}$, consuming $5$ stamina.

Data Range

For $50\%$ of the data: $1 \leq n \leq 1000$, $1 \leq h \leq 10^9$.
For $100\%$ of the data: $1 \leq n \leq 500000$, $1 \leq h \leq 10^9$.

All data guarantee that the shortest and tallest mountains are unique.

见题面 Input 部分

见题面 Output 部分