该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个序列 $\{a_n\}$。

对于每一个连续的区间 $[l,r]$，记它的神奇值为这个区间中最大值与最小值的差。那么序列 $\{a_n\}$ 的总的神奇程度就是每一个区间 $[l,r] \ (1\le l\le r\le n)$ 的神奇值之和。

求序列 $\{a_n\}$ 的总的神奇程度。

第二行，$n$个整数，第$i$个数$a_i$。

Output Format

共一行，一个整数表示总的神奇值。

Sample

输入样例：

3
2 3 3

输出样例：

2

Hint

数据范围

对于$20\%$的数据，满足$n \le 200$；

对于$60\%$的数据，满足$n \le 3000$；

对于$100\%$的数据，满足$n\le 500000,c_i\le 10^6$。

提示

可能需要使用64位长整型（long long / int64）。

保证时限为标程的4倍以上，但是建议使用较快的输入方式，不建议采用cin等读入方式。