分析

• 分析题目可知，对于$a_i$，我们需要在$a_0,…,a_{i-1}$中找到与$a_i$最近接的一个数。目前没有数据结构支持这种操作，我们可以将这个操作分解，及在这些树中找到$a_i$的前驱和后继，两者取更接近的一个即可。

• 总结一下，这个题目存在的操作：

（1）插入某个数；

（2）找到大于等于某个数的最小数；

（3）找到小于等于某个数的最大数；

• 因此，这一题可以使用set来求解，set中的lower_bound(x)可以返回大于等于x的最小数；upper_bound(x)可以返回大于x的最小数，之后将返回结果减减就可以得到小于等于x的最大数。

• 这是使用Treap实现这些操作。

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 33010, INF = 1e7;

int n;
struct Node {
    int l, r;  // 左右孩子的编号
    int key, val;
} tr[N];

int root, idx;

int get_node(int key) {

    tr[++idx].key = key;
    tr[idx].val = rand();
    return idx;
}

// 右旋
void zig(int &p) {

    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
}

// 左旋
void zag(int &p) {

    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
}

void build() {

    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    if (tr[1].val < tr[2].val) zag(root);
}

void insert(int &p, int key) {

    if (!p) p = get_node(key);
    else if (tr[p].key == key) return;
    else if (tr[p].key > key) {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);
    } else {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);
    }
}

int get_prev(int p, int key) {  // 找到小于等于key的最大数

    if (!p) return -INF;
    if (tr[p].key > key) return get_prev(tr[p].l, key);
    // 说明tr[p].key <= key
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) {  // 找到大于等于key的最小数

    if (!p) return INF;
    if (tr[p].key < key) return get_next(tr[p].r, key);
    // 说明tr[p].key >= key
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {

    build();

    scanf("%d", &n);

    LL res = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (i == 1) res += x;
        else res += min(x - get_prev(root, x), get_next(root, x) - x);

        insert(root, x);
    }

    printf("%lld\n", res);

    return 0;
}