4024: 子串的最大差

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:17 通过:7

题目描述

定义序列的最大差为序列中最大数与最小数的差。比如(3,1,4,5,6) 的最大差为 6−1=5 , (2,2) 的最大差为 2−2=0。

定义一个序列的子串为该序列中连续的一段序列。

给定一个长度为 n 的数组 a1,a2,…,an,请求出这个序列的所有子串的最大差之和。


输入格式

第一行一个数字 n

接下来一行 n 个整数 a1,a2,…,an

输出格式

一个数,表示答案。

所有数据保证 1≤n≤500000,0≤ai≤108

输入样例 复制

3
1 2 3

输出样例 复制

4