题目描述

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

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

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

（术语说明：子串是指原序列中连续的一段元素，例如对于序列 $(1,2,3,4)$，其子串有 $(1,2)$、$(2,3,4)$ 等。）

输入格式

第一行一个整数 $n$。

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

输出格式

输出一个整数，表示所有子串的最大差之和。

样例输入

3
1 2 3

样例输出

4

数据范围

所有数据保证 $1 \le n \le 5 \times 10^5$，$0 \le a_i \le 10^8$。