【普及】子数组的最值之差
给你一个长度为 n 的数组 a，定义：
$$f(l, r) = \max\{a_l, a_{l+1}, \cdots, a_r\} - \min\{a_l, a_{l+1}, \cdots, a_r\}$$
请你计算下面式子的结果：
i=1∑nj=i∑nf(i,j)
简单来说：
- f(l,r)：表示 子数组 [al,al+1,⋯,ar] 中的 最大值与最小值之差
- 求所有子数组的 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≤n≤105
- 0≤ai≤105
请思考后再点击查看提示
来源
