【普及】子数组的最小值之和

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

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

简单来说：

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

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

输入格式

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

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

输出格式

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

3
2 1 3

9

4
3 1 2 4

17

3
1 1 1

6

提示

【样例 1 解释】

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

【数据范围】

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

来源

• 参考答案