#9253. [DAY15]子串波动值之和 暂未评定

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

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

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

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

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

第二行包含 个整数 ，表示序列中的元素。

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

样例输入 1

3
3 1 2

样例输出 1

5

对于 的数据，，。

• 子任务 1（30 分）：。
• 子任务 2（30 分）：。
• 子任务 3（40 分）：没有特殊限制。