#B. [COCI2010-2011#3] DIFERENCIJA

Type: RemoteJudge

1000ms

64MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出一个长度为 $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) $$

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

输入第一行一个整数 $n$ ，表示序列的长度。

接下来的 $n$ 行，每行一个整数 $a_i$ ，描述这个序列。

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

对于 $100\%$ 的数据，保证 $2\le n\le 3\times 10^5$ ， $1\le a_i\le 10^8$ 。

题目译自 COCI2010-2011 CONTEST #3 T5 DIFERENCIJA。