题目描述

33DAI 最近对序列产生了浓厚的兴趣。他有一个长度为 $n$ 的整数序列 $A$。

他定义了一个区间的“波动值”。对于序列 $A$ 的一个连续子区间 $[l, r]$（即从 $a_l$ 到 $a_r$ 的所有元素），其“波动值”为该区间的最大值与最小值的差。

例如，对于序列 [3, 1, 4]，子区间 [3, 1] 的波动值为 $3 - 1 = 2$；子区间 [1, 4] 的波动值为 $4 - 1 = 3$。

现在，33DAI 想知道，这个序列 所有 可能的连续子区间的“波动值”之和是多少。答案可能很大，请对 $998244353$ 取余。

输入格式

第一行包含一个正整数 $n$，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。

输出格式

输出一个整数，表示所有连续子区间的“波动值”之和，对 $998244353$ 取余的结果。

3
3 1 2

5

样例解释 1

序列 [3, 1, 2] 的所有连续子区间及其波动值如下：

• [3]: $\max(3) - \min(3) = 0$
• [1]: $\max(1) - \min(1) = 0$
• [2]: $\max(2) - \min(2) = 0$
• [3, 1]: $\max(3, 1) - \min(3, 1) = 3 - 1 = 2$
• [1, 2]: $\max(1, 2) - \min(1, 2) = 2 - 1 = 1$
• [3, 1, 2]: $\max(3, 1, 2) - \min(3, 1, 2) = 3 - 1 = 2$

总和为 $0 + 0 + 0 + 2 + 1 + 2 = 5$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$。

• 子任务 1（30 分）：$1 \le n \le 200$。
• 子任务 2（30 分）：$1 \le n \le 2000$。
• 子任务 3（40 分）：没有特殊限制。