8940: 洛谷P6503 - [COCI2010-2011#3] DIFERENCIJA
[Creator : ]
Description
给出一个长度为 $n$ 的序列 $a_i$，求出下列式子的值：
$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)$
即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。
说明
题目译自 [COCI2010-2011] CONTEST #3 T5 DIFERENCIJA。
$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)$
即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。
说明
题目译自 [COCI2010-2011] CONTEST #3 T5 DIFERENCIJA。
Input
输入第一行一个整数 $n$，表示序列的长度。
接下来的 $n$ 行，每行一个整数 $a_i$，描述这个序列。
接下来的 $n$ 行，每行一个整数 $a_i$，描述这个序列。
Output
输出一行一个整数，表示式子的答案。
Constraints
对于 $100\%$ 的数据，保证 $2\le n\le 3\times 10^5$，$1\le a_i\le 10^8$。
Sample 1 Input
3
1
2
3
Sample 1 Output
4
Sample 2 Input
4
7
5
7
5
Sample 2 Output
12
Sample 3 Input
4
3
1
7
2
Sample 3 Output
31
HINT
相同题目：洛谷P6503。