P6375 "StOI-1" Xiao Z's Trip

On an open field, there are $n$ mountains. Each mountain has a height value $h$. Xiao Z is on the highest mountain and wants to go to the lowest mountain. He can move in the following ways: $1.$ Move to a mountain that is lower than the current mountain. $2.$ Move to a mountain with the same height as the current mountain (he cannot stay on the current mountain). For each height, this move can only be used once (that is, he cannot arrive at mountains of the same height $3$ times in a row or more). Each move costs stamina. The stamina cost is the horizontal distance between the two mountains (if he moves from mountain $i$ to mountain $j$, it costs |$i-j$| stamina). Each time Xiao Z has multiple possible moves, he will choose one uniformly at random. Find the expected stamina cost, and output the result modulo $998,244,353$.

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

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

--- #### Sample 1 Explanation The value before taking modulo is $\frac{10}{3}$. The possible paths are as follows (numbers represent mountain indices): 1. $(4,1)$ with probability $\frac{1}{3}$, stamina cost $3$; 2. $(4,3,1)$ with probability $\frac{1}{3}$ $\times$ $\frac{1}{2}$, stamina cost $3$; 3. $(4,2,1)$ with probability $\frac{1}{3}$ $\times$ $\frac{1}{2}$, stamina cost $3$; 4. $(4,3,2,1)$ with probability $\frac{1}{3}$ $\times$ $\frac{1}{2}$, stamina cost $3$; 5. $(4,2,3,1)$ with probability $\frac{1}{3}$ $\times$ $\frac{1}{2}$, stamina cost $5$. --- #### Constraints For $50$% of the testdata: $1 \le n \le 1000$, $1 \le h \le 10^{9}$. For $100$% of the testdata: $1 \le n \le 500000$, $1 \le h \le 10^{9}$. For all testdata: the lowest and highest mountain heights are unique. Translated by ChatGPT 5