【普及】子数组的最值之差

给你一个长度为 $n$ 的数组 $a$，定义：

$$f(l, r) = \max\{a_l, a_{l+1}, \cdots, a_r\} - \min\{a_l, a_{l+1}, \cdots, a_r\}$$

请你计算下面式子的结果：

$$\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)$$

简单来说：

• $f(l, r)$：表示 子数组 $[a_l, a_{l+1}, \cdots, a_{r}]$ 中的 最大值与最小值之差
• 求所有子数组的 $f(l, r)$，再相加，求最后的总和

由于答案可能很大，你只需要输出答案对 998244353 取模后的结果

输入格式

第一行包含一个整数 $n$ 代表数组长度；

第二行包含 $n$ 个整数表示数组 $a$

输出格式

对于每组数据输出一行，包含答案

3
2 1 3

5

提示

【样例 1 解释】

• $f([2]) = 2 - 2 = 0$
• $f([2, 1]) = 2 - 1 = 1$
• $f([2, 1, 3]) = 3 - 1 = 2$
• $f([1]) = 1 - 1 = 0$
• $f([1, 3]) = 3 - 1 = 2$
• $f([3]) = 3 - 3 = 0$
• 结果为：$0+1+2+0+2+0=5$

【数据范围】

• $1 \le n \le 10^5$
• $0 \le a_i \le 10^5$

请思考后再点击查看提示

来源

• 参考答案