#A135. [COCI2010-2011#3] DIFERENCIJA

[COCI2010-2011#3] DIFERENCIJA

题目描述

给出一个长度为 nn 的序列 aia_i,求出下列式子的值:

i=1nj=inmaxikjakminikjak\sum_{i=1}^{n} \sum_{j=i}^{n} \max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k

即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。

输入格式

输入第一行一个整数 nn,表示序列的长度。

接下来的 nn 行,每行一个整数 aia_i,描述这个序列。

输出格式

输出一行一个整数,表示式子的答案。

3
1
2
3
4
4
7
5
7
5
12
4
3
1
7
2
31

提示

数据规模与约定

对于 100%100\% 的数据,保证 2n3×1052\le n\le 3\times 10^51ai1081\le a_i\le 10^8