0x40数据结构进阶（练习）9：营业额统计

P2234 [HNOI2002] 营业额统计

题目描述

给出 $n$ 个数 $a_i$，每个数的最小波动值 $= min{ | a_i - a_j | , 1<=j< i }$， 求 $n$ 个数的最小波动值之和。

【输入格式】

第一行一个正整数 $n \ (1 \le n \le 10^5)$，下来 $n$ 个整数 $a_i \ (|a_i| \le 10^9)$ 。

【输出格式】

一个正整数，即n个数的最小波动值之和。

【样例输入】

6
5 1 2 5 4 6

【样例输出】

12

【数据提示】

结果说明：$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$