连续子序列的权值

题目

知识点：单调栈

我们定义连续序列$a[p],a[p+1]....a[q]$的权值为$max$$(a[p],a[p+1]....a[q]) $- $min$$(a[p],a[p+1]....a[q])$，给定一个由$N$个整数组成的序列，请求出所有连续子序列的权值和。

输入

第$1$行：1个数$N$，表示数组的长度。$(1 <= N <= 50000)$

第$2 - N + 1$行：每行1个数，表示数组中的元素$(1 <= A[p] <= 50000)$

输出

输出所有连续子序列的权值和。

输入样例

5
1
2
3
4
5

输出样例

20