Problem2288--Imbalanced Array

2288: Imbalanced Array

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

对于给定由 n 个元素构成的数组。一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。
以下是数组[1,4,1]不平衡值为9的例子,共有6个子序列:
[1] (从第一号到第一号)不平衡值为 0;
[1, 4] (从第一号到第二号), 不平衡值为 3;
[1, 4, 1] (从第一号到第三号),不平衡值为 3;
[4] (从第二号到第二号),不平衡值为 0;
[4, 1] (从第二号到第三号),不平衡值为 3;
[1] (从第三号到第三号)不平衡值为 0;

Input

一个整数n
n个整数第i个数表示a[i]

Output

一个整数表示数组的不平衡值

Sample Input Copy

3
1 4 1

Sample Output Copy

9

Source/Category

  单调栈 CF