题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。

经济管理学上定义了一种最小波动值来衡量这种情况：记该天以前某一天的营业额为 $a_i$ ，该天营业额为 $b$，则该天的最小波动值 $\delta=\min|a_i-b|$。当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。

你的任务就是编写一个程序帮助 Tiger 来计算这一个值，第一天的最小波动值为第一天的营业额。

一句话题意：给出一个 $n$ 个数的数列 $\{a_n\}$，对于第 $i$ 个元素 $a_i$ ，定义 $f_i=\min_{1\le j<i}|a_i-a_j|$，其中 $f_1=a_1$ 。求 $\sum_{i=1}^n f_i$ 。

输入格式

第一行为正整数 $n$，表示该公司从成立一直到现在的天数；

接下来的 $n$ 行每行有一个正整数，表示第 $i$ 天公司的营业额 $a_i$ 。

输出格式

仅有一个正整数，即每一天最小波动的和，结果不超过 $2^{31}$ 。

样例

输入样例 1

6
5
1
2
5
4
6

输出样例 1

12

样例说明

营业额依次为：$5,1,2,5,4,6$

• 第 $1$ 天：$f_1 = 5$
• 第 $2$ 天：$\min|1-5|=4$，$f_2=4$
• 第 $3$ 天：$\min(|2-5|,|2-1|)=\min(3,1)=1$，$f_3=1$
• 第 $4$ 天：$\min(|5-5|,|5-1|,|5-2|)=\min(0,4,3)=0$，$f_4=0$
• 第 $5$ 天：$\min(|4-5|,|4-1|,|4-2|,|4-5|)=\min(1,3,2,1)=1$，$f_5=1$
• 第 $6$ 天：$\min(|6-5|,|6-1|,|6-2|,|6-5|,|6-4|)=\min(1,5,4,1,2)=1$，$f_6=1$

总和：$5+4+1+0+1+1=12$

数据范围

• $1 \le n < 2^{15}$
• $a_i \le 10^6$

时间限制：1000 ms
内存限制：524288 KB

提示

本题可以看作动态维护一个集合，支持插入元素，并查询与给定值最接近的元素（前驱或后继），然后取差值的最小值。

可以使用平衡树（如 Treap、Splay、红黑树）或 C++ STL 中的 set 来维护已出现的营业额，每次插入 $a_i$ 前，用 lower_bound 找到大于等于 $a_i$ 的第一个数（后继），并用 prev 找到前驱，计算与两者的差值的最小值，累加到答案中。注意第一天直接插入并累加 $a_1$。

注意： $a_i$ 可能重复，但重复时最小波动值为 $0$（因为 $|a_i-a_j|=0$）。因此可以用 multiset 或允许重复的平衡树。

算法步骤：

1. 初始化答案 $ans = 0$，初始化一个空的平衡树（如 set<int>）。
2. 读入 $n$ 和第一个数 $x$，$ans += x$，将 $x$ 插入集合。
3. 对于 $i=2$ 到 $n$：
   • 读入 $x$。
   • 在集合中查找 $x$ 的后继 $s$（第一个 $\ge x$ 的数）和前驱 $p$（最后一个 $< x$ 的数）。
   • 计算 $d = \min(|x-s|, |x-p|)$（注意前驱或后继可能不存在，需要特判）。
   • $ans += d$。
   • 将 $x$ 插入集合。
4. 输出 $ans$。

时间复杂度：$O(n \log n)$，对于 $n < 32768$ 完全足够。