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

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

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$，请求出这个序列的所有子串的最大差之和。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一个数，表示答案。

样例输入

3
1 2 3

样例输出

4

数据规模

所有数据保证 $1\leq n\leq 500000, 0 \leq a_i \leq 10^8$。