题目描述

对于给定由 $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$ 号到第 $3$ 号)，不平衡值为 $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)$，表示数组的元素。

输出格式

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

3
1 4 1

9

说明/提示

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

1
1000000

0

2
313753 313753

0