CF817D Imbalanced Array

对于给定由 $n$ 个元素构成的数组。一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。 以下是数组 $[1,4,1]$ 不平衡值的例子，共有 $6$ 个子序列： - $[1]$ (从第 $1$ 号到第 $1$ 号)，不平衡值为 $1-1=0$。 - $[1, 4$] (从第 $1$ 号到第 $2$ 号), 不平衡值为 $4-1=3$。 - $[1, 4, 1]$ (从第 $1$ 号到第 $3$ 号)，不平衡值为 $4-1=3$。 - $[4]$ (从第 $2$ 号到第 $2$ 号)，不平衡值为 $4-4=0$。 - $[4, 1]$ (从第 $2$ 号到第 $2$ 号)，不平衡值为 $4-1=3$。 - $[1]$ (从第 $3$ 号到第 $3$ 号)，不平衡值为 $1-1=0$。 综上所述，数组的不平衡值为 $3+3+3=9$。

输入共 $2$ 行。 第一行包含一个正整数 $n(1 \le n \le 10^6)$，表示数组元素的个数。 第一行包含 $n$ 个正整数 $a_1,a_2 \dots a_n(1 \le a_i \le 10^6)$，表示数组的元素。

仅一行，即数组的不平衡值。

对于 $100 \%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^6$。