此处为代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e4+10,INF = 1e9;
typedef long long ll;
struct node{
    int s[2],p,v;
    int size;
    void init(int _p,int _v){
        p = _p;
        v = _v;
        size = 1;
    }
}tr[N];
int root,idx;
void pushup(int x){
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x){
    int y = tr[x].p ,z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k^1];
    tr[tr[x].s[k^1]].p = y;
    tr[x].s[k^1] = y;
    tr[y].p = x;
    pushup(y);
    pushup(x);
}
void splay(int x,int k){
    while(tr[x].p != k){
        int y = tr[x].p,z = tr[y].p;
        if(z!=k)
            if((tr[y].s[1] == x)^(tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}
void insert(int v){
    int u = root,p = 0;
    while(u) p = u,u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(p,v);
    splay(u,0);
}
int get_prev(int v){
    int u = root,res = -INF;
    while(u){
        if(tr[u].v <= v) res = max(res,tr[u].v),u = tr[u].s[1];
        else u = tr[u].s[0];
    }
    return res;
}
int get_next(int v){
    int u = root,res = INF;
    while(u){
        if(tr[u].v >= v) res = min(res,tr[u].v),u = tr[u].s[0];
        else u = tr[u].s[1];
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    insert(-INF);
    insert(INF);
    insert(x);
    ll res = x;
    --n;
    while(n--){
        cin>>x;
        int a = get_prev(x);
        int b = get_next(x);
        res+=min(abs(a-x),abs(b-x));
        insert(x);
    }
    cout<<res<<endl;
    return 0;
}