P6375 「StOI-1」小Z的旅行

一块空地，有$n$座山，每座山有一个高度值$h$。小Z在最高的山上，要去最低的山。 他有如下移动方案： $1.$ 移动到一座比当前山低的山； $2.$ 移动到和当前山一样高的山（不可停留在当前山），对于每一高度只能执行一次该方案（即不可以连续 $3$ 次或以上到达同一高度的山）。 每次移动都会耗费体力值，耗费的体力值为两座山的水平距离（若从第 $i$ 座山移动到第 $j$ 座山，则耗费 |$i-j$| 点体力值）。 小Z**每次**若有多种方案移动，则会**等概率**选择任意一种，求耗费体力值的期望对 $998,244,353$ 取余后的结果。

无

无

--- #### 样例1解释 取模前值为 $\frac{10}{3}$。 有如下方案（数字代表山的编号）： 1. $(4,1)$ 概率 $\frac{1}{3}$ ， 耗费体力值 $3$ ； 2. $(4,3,1)$ 概率 $\frac{1}{3}$ $\times$ $\frac{1}{2}$ ，耗费体力值 $3$ ； 3. $(4,2,1)$ 概率 $\frac{1}{3}$ $\times$ $\frac{1}{2}$ ，耗费体力值 $3$ ； 4. $(4,3,2,1)$ 概率 $\frac{1}{3}$ $\times$ $\frac{1}{2}$ ，耗费体力值 $3$ ； 5. $(4,2,3,1)$ 概率 $\frac{1}{3}$ $\times$ $\frac{1}{2}$ ，耗费体力值 $5$ 。 --- #### 数据范围 对于 $50$% 的数据：$1 ≤ n ≤ 1000$，$1 ≤ h ≤ 10^{9}$； 对于 $100$% 的数据：$1 ≤ n ≤ 500000$，$1 ≤ h ≤ 10^{9}$。 所有数据：最低和最高的山高度唯一。