题目描述

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

一个序列的子串定义为该序列中连续的一段子序列。比如 $(1,2,3)$ 有 $6$ 个子串，分别是

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

输入格式

第一行：单个整数 $n$ 第二行：$n$ 个整数表示 $a_1,\dots,a_n$，

输出格式

单个正整数：表示所有子串的最大差之和。

3
1 2 3

4

数据范围

• 对于 $30\%$ 的数据，$n\leq 500$
• 对于 $60\%$ 的数据，$n\leq 20,000$
• 对于 $100\%$ 的数据，$n\leq 500,000$
• $0\leq a_{i}\leq 10^8$