Imbalanced Array

题意翻译

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

题目描述

You are given an array $ a $ consisting of $ n $ elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array. For example, the imbalance value of array $ [1,4,1] $ is $ 9 $ , because there are $ 6 $ different subsegments of this array: - $ [1] $ (from index $ 1 $ to index $ 1 $ ), imbalance value is $ 0 $ ; - $ [1,4] $ (from index $ 1 $ to index $ 2 $ ), imbalance value is $ 3 $ ; - $ [1,4,1] $ (from index $ 1 $ to index $ 3 $ ), imbalance value is $ 3 $ ; - $ [4] $ (from index $ 2 $ to index $ 2 $ ), imbalance value is $ 0 $ ; - $ [4,1] $ (from index $ 2 $ to index $ 3 $ ), imbalance value is $ 3 $ ; - $ [1] $ (from index $ 3 $ to index $ 3 $ ), imbalance value is $ 0 $ ; You have to determine the imbalance value of the array $ a $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1<=n<=10^{6} $ ) — size of the array $ a $ . The second line contains $ n $ integers $ a_{1},a_{2}...\ a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) — elements of the array.

输出格式

Print one integer — the imbalance value of $ a $ .

输入输出样例

输入样例 #1

3
1 4 1

输出样例 #1

9