$\color{red}{Splay 大法好！}$

这里提供一个 Splay 的解答。

分析

差不多就是一道平衡树的板子题。
题目要我们求出新插入的数与之前的数的差的绝对值最小，那么我们就想到建一棵平衡树，然后求一下新插入数的前驱和后继就好了，需要特殊判断的地方是有可能新插入的数与之前的数相等，这样对应的贡献必然是 $0$ ，那就多维护一个属性 $cnt$ 如果 $cnt>1$ ，说明出现新插入的数与之前的数相等的情况。

#pragma GCC optimize("O3")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
const int N=35005;

int n;

struct node{
    int s[2],p,v;
    int cnt;

    void init(int _p,int _v){
        p=_p;
        v=_v;
        cnt=1;
    }
}tr[N];
int root,idx;

void rotate(int x){
    int y=tr[x].p, z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[x].p=z, tr[z].s[tr[z].s[1]==y]=x;
    tr[y].s[k]=tr[x].s[k^1], tr[tr[x].s[k^1]].p=y;
    tr[y].p=x, tr[x].s[k^1]=y;
}

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[z].s[0]==y) ^ (tr[y].s[0]==x)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(k==0) root=x;
}

void insert(int v){
    int u=root, p=0;
    while(u && tr[u].v!=v) p=u, u=tr[u].s[v>tr[u].v];
    if(u) {
        tr[u].cnt++;
        return;
    }
    else{
        u=++idx;
        if(p) tr[p].s[v>tr[p].v]=u;
        tr[u].init(p,v);    
    }
    splay(u,0);
}

void find(int v){
    int u=root;
    while(tr[u].v!=v && tr[u].s[v>tr[u].v]) u=tr[u].s[v>tr[u].v];
    splay(u,0);
}

int pre(int v){
    find(v);
    int u=root;
    if(tr[u].v<v) return u;
    u=tr[u].s[0];
    while(tr[u].s[1]) u=tr[u].s[1];
    return u;
}

int suf(int v){
    find(v);
    int u=root;
    if(tr[u].v>v) return u;
    u=tr[u].s[1];
    while(tr[u].s[0]) u=tr[u].s[0];
    return u;
}

int main(){
    long long res=0;
    cin>>n;
    insert(-INF), insert(INF);
    int k; cin>>k;

    res+=k;
    insert(k);

    for(int i=2;i<=n;i++){
        int k; cin>>k;
        insert(k);
        find(k);
        if(tr[root].cnt>1) continue;
        res+=min(abs(k-tr[pre(k)].v),abs(tr[suf(k)].v-k));
    }
    cout<<res<<'\n';

    return 0;
}

upd: 2022.1.18
附上 fhq treap 的做法~

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5, INF=1e9;

struct Node{
    int l, r;
    int key;
    int sz, v;

    #define ls tr[u].l
    #define rs tr[u].r
}tr[N];

int root, idx;

void pushup(int u){
    tr[u].sz=tr[ls].sz+tr[rs].sz+1;
}

int add(int v){
    ++idx;
    tr[idx].key=rand(), tr[idx].sz=1, tr[idx].v=v;
    return idx;
}

int merge(int x, int y){
    if(!x || !y) return x+y;
    if(tr[x].key>tr[y].key){
        tr[x].r=merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else{
        tr[y].l=merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

void split(int u, int val, int &x, int &y){
    if(!u) return x=y=0, void();
    if(tr[u].v<=val)
        x=u, split(rs, val, rs, y);
    else
        y=u, split(ls, val, x, ls);
    pushup(u);
}

void insert(int v){
    int x, y;
    split(root, v, x, y);
    root=merge(x, merge(add(v), y));
}

bool exist(int v){
    int x, y, z;
    split(root, v, x, z);
    split(x, v-1, x, y);
    bool res=y? 1: 0;
    merge(x, merge(y, z));
    return res;
}

int val4rk(int v){
    int x, y;
    split(root, v-1, x, y);
    int res=tr[x].sz+1;
    root=merge(x, y);
    return res;
}

int rk4val(int k){
    int u=root;
    while(u){
        if(tr[ls].sz+1==k) return tr[u].v;
        else if(tr[ls].sz>=k) u=ls;
        else k-=tr[ls].sz+1, u=rs;
    }
    return -1;
}

int get_prev(int v){
    int x, y;
    split(root, v-1, x, y);
    int u=x;
    while(rs) u=rs;
    int res=tr[u].v;
    root=merge(x, y);
    return res;
}

int get_next(int v){
    int x, y;
    split(root, v, x, y);
    int u=y;
    while(ls) u=ls;
    int res=tr[u].v;
    root=merge(x, y);
    return res;
}

int main(){
    srand(131);
    int n; cin>>n;
    int x; cin>>x;
    insert(-INF), insert(INF);
    insert(x);
    ll res=x;

    rep(i,1,n-1){
        read(x);
        if(exist(x)) continue;
        res+=min(x-get_prev(x), get_next(x)-x);
        insert(x);
    }

    cout<<res<<endl;

    return 0;
}