前几篇的平衡树题解，个人觉得有点复杂。
这是没有用到平衡树的题解，来个排序的：

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int main(){
    cin.sync_with_stdio(false);
    int n;cin>>n;
    int *a=new int[n];
    for(int i=0;i<n;i++)cin>>a[i];
    int *order=new int[n]; // 索引数组，排序后的a
    int *idx=new int[n]; // 每个a的索引在order中出现的位置
    for(int i=0;i<n;i++)order[i]=i;
    //for(int i=0;i<n-1;i++){
    //    for(int j=0;j<n-i-1;j++){
    //        if(a[order[j]]>a[order[j+1]])swap(order[j],order[j+1]);
    //    }
    //}
    sort(order, order+n, [&a](int m, int n) {
        return a[m]<a[n]; // 升序
    });
    for(int i=0;i<n;i++)idx[order[i]]=i;

    long long total=a[0];
    for(int i=1;i<n;i++){ //i:a的索引
        int min_dt_l=INT_MAX,min_dt_r=INT_MAX;
        int index=idx[i]; //index:idx中i元素对应的索引
        int l=index-1,r=index+1; // l,r:idx的索引
        while(l>=0 || r<n){
            // 需要同时找到左边和右边的最小波动值
            if(l>=0){
                int idx_l=order[l]; //idx_l,idx_r:a的索引
                if(idx_l<i) // 如果时间在i前面
                    min_dt_l=min(min_dt_l,a[i]-a[idx_l]);
            }
            if(r<n){
                int idx_r=order[r];
                if(idx_r<i)
                    min_dt_r=min(min_dt_r,a[idx_r]-a[i]);
            }
            if((l<0 || min_dt_l!=INT_MAX) && (r>=n || min_dt_r!=INT_MAX))break;
            if(l>=0)l--;
            if(r<n)r++;
        }
        int min_dt=min(min_dt_l,min_dt_r);
        total+=min_dt;
    }
    cout<<total<<endl;
    return 0;
}