CF817D.Imbalanced Array

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.

给你一个包含 $n$ 个元素的数组 $a$。该数组某个子段（连续子数组）的不平衡值定义为该子段中最大值与最小值之差。整个数组的不平衡值则定义为该数组所有子段的不平衡值之和。

例如，数组 $[1,\,4,\,1]$ 的不平衡值为 $9$，因为该数组共有 $6$ 个不同的子段：

• $[1]$（下标从 $1$ 到 $1$），不平衡值为 $0$；
• $[1,\,4]$（下标从 $1$ 到 $2$），不平衡值为 $3$；
• $[1,\,4,\,1]$（下标从 $1$ 到 $3$），不平衡值为 $3$；
• $[4]$（下标从 $2$ 到 $2$），不平衡值为 $0$；
• $[4,\,1]$（下标从 $2$ 到 $3$），不平衡值为 $3$；
• $[1]$（下标从 $3$ 到 $3$），不平衡值为 $0$。

你需要计算数组 $a$ 的不平衡值。

The first line contains one integer n (1 ≤ n ≤ 106) — size of the array a.

The second line contains n integers _a_1, _a_2... a__n (1 ≤ a__i ≤ 106) — elements of the array.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）—— 数组的元素。

Print one integer — the imbalance value of a.

输出一个整数——数组 $a$ 的不平衡值。