题目描述

一块空地，有$n$座山，每座山有一个高度值$h$。小Z在最高的山上，要去最低的山。

他有如下移动方案：

$1.$ 移动到一座比当前山低的山；

$2.$ 移动到和当前山一样高的山（不可停留在当前山），对于每一高度只能执行一次该方案（即不可以连续 $3$ 次或以上到达同一高度的山）。

每次移动都会耗费体力值，耗费的体力值为两座山的水平距离（若从第 $i$ 座山移动到第 $j$ 座山，则耗费 |$i-j$| 点体力值）。

小Z每次若有多种方案移动，则会等概率选择任意一种，求耗费体力值的期望对 $998,244,353$ 取余后的结果。

输入格式

第一行一个正整数 $n$ ，表示山的个数。 接下来一行 $n$ 个正整数，表示每座山的高度。

输出格式

一个整数，表示最终答案对 $998,244,353$ 取余后的结果。

4
1 3 3 7

332748121

3
1 3 2

2

10
1 2 2 2 4 3 2 6 5 9

384244861

提示

样例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}$。

所有数据：最低和最高的山高度唯一。