这里采用 Treap 平衡树。

基本平衡树操作。

插入不必多说，对于每次统计，查询前驱后继再取差值最小值即可。

注意第一个数由于最开始只有两个哨兵，所以会出现无穷的情况，特判即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 15, INF = 0x3f3f3f3f;
int rt, n;

struct Treap {
    int ls, rs;
    int val, prio;
    int cnt, sz;
} tr[N];

int tot = 0;
int get_node(int x) {
    tr[++tot].val = x;
    tr[tot].prio = rand();
    tr[tot].cnt = tr[tot].sz = 1;
    return tot;
}

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

void zag(int &x) {
    int y = tr[x].rs;
    tr[x].rs = tr[y].ls, tr[y].ls = x, x = y;
    pushup(tr[x].ls); pushup(x);
}

void zig(int &x) {
    int y = tr[x].ls;
    tr[x].ls = tr[y].rs, tr[y].rs = x, x = y;
    pushup(tr[x].rs); pushup(x);
}

void insert(int &u, int val) {
    if (!u) u = get_node(val);
    else if (tr[u].val == val) {
        tr[u].cnt++;
    } else {
        if (val < tr[u].val) {
            insert(tr[u].ls, val);
            if (tr[tr[u].ls].prio > tr[u].prio) zig(u);
        } else {
            insert(tr[u].rs, val);
            if (tr[tr[u].rs].prio > tr[u].prio) zag(u);
        }
    }
    pushup(u);
}

//注意这里前驱后继是可以相等的
int pre(int u, int val) {
    if (!u) return -INF;
    if (tr[u].val == val) return val;
    if (val < tr[u].val) return pre(tr[u].ls, val);
    else return max(tr[u].val, pre(tr[u].rs, val));
}

int nxt(int u, int val) {
    if (!u) return INF;
    if (tr[u].val == val) return val;
    if (val > tr[u].val) return nxt(tr[u].rs, val);
    else return min(tr[u].val, nxt(tr[u].ls, val));
}

void build() {
    get_node(-INF), get_node(INF);
    rt = 1, tr[rt].rs = 2;
    if (tr[2].prio > tr[1].prio) zag(rt);
}

int ans = 0;

int main() {
    srand(time(0));
    build();
    scanf("%d", &n);
    int x; scanf("%d", &x); ans += x; insert(rt, x);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);
        ans += min(x - pre(rt, x), nxt(rt, x) - x);
        insert(rt, x);
    }
    printf("%d\n", ans);
    return 0;
}