题目描述

对于给定由 $n$ 个元素构成的数组。一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。

以下是数组 $[1,4,1]$ 不平衡值为 $9$ 的例子，共有 $6$ 个子序列：

• $[1]$，从第一号到第一号，不平衡值为 $0$；
• $[1, 4]$，从第一号到第二号，不平衡值为 $3$；
• $[1, 4, 1]$，从第一号到第三号，不平衡值为 $3$；
• $[4]$，从第二号到第二号，不平衡值为 $0$；
• $[4, 1]$，从第二号到第三号，不平衡值为 $3$；
• $[1]$，从第三号到第三号，不平衡值为 $0$。

输入格式

第一行一个整数 $n$，$1 \le n \le 10^6$。

第二行 $n$ 个整数 $a_i$，$1 \le a_i \le 10^6$。

输出格式

一个整数表示答案。

3
1 4 1

9