1. 题目

传送门=￣ω￣=

2. 题解

平衡树模板题
写个 treap，资瓷找前驱、找后驱、插入即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct N{LL d,f,s;N*l,*r;N();}*def=new N;
N::N(){d=f=s=0;l=r=def;}
struct treap
{
    N*root;
    treap(){root=def;}
    void update(N*&a){a->s=a->l->s+a->r->s+1;}
    void lrot(N*&a){N*b=a->r;a->r=b->l,b->l=a,b->s=a->s,update(a),a=b;}
    void rrot(N*&a){N*b=a->l;a->l=b->r,b->r=a,b->s=a->s,update(a),a=b;}
    void insert(N*&a,LL data)
    {
        if(a==def)
        {
            a=new N;
            a->d=data,a->f=rand(),a->s=1;
            return;
        }
        if(data<a->d){if(insert(a->l,data),a->l->f<a->f)rrot(a);}
        else if(data>a->d)if(insert(a->r,data),a->r->f<a->f)lrot(a);
        update(a);
    }
    LL pre(N*&a,LL data)
    {
        if(a==def)return (LL)-1e8;
        if(a->d==data)return a->d;
        if(a->d<data)return max(a->d,pre(a->r,data));
        return pre(a->l,data);
    }
    LL nxt(N*&a,LL data)
    {
        if(a==def)return (LL)1e8;
        if(a->d==data)return a->d;
        if(a->d>data)return min(a->d,nxt(a->l,data));
        return nxt(a->r,data);
    }
}t;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();bool flag=0;dig=0;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')flag=1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
LL n,ans;
int main()
{
    IN(n),IN(ans),t.insert(t.root,ans),srand(n);
    for(LL i=2,a,pre,nxt;i<=n;i++)
        IN(a),ans+=min(a-t.pre(t.root,a),t.nxt(t.root,a)-a),t.insert(t.root,a);
    printf("%lld\n",ans);
    return 0;
}