0分 有旋 Treap 求调。

#include<bits/stdc++.h>
#define ll long long
#define MAXN 1000010
#define INF 2147483647
#define int long long
using namespace std;
struct node{
    int ls,rs,siz,sm,rk;
    ll val;
}tree[MAXN];
int n,root,ps;
ll ans;
int qread()
{
    int sum=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-48;ch=getchar();}
    return sum*f;
}
void qprintll(int x)
{
    if(x>9) qprintll(x/10);
    putchar(x%10+48);
}
void qpll(int x)
{
    if(x<0) x=-x,putchar('-');
    qprintll(x);
    return;
}
void update(int x)
{
    tree[x].siz=tree[tree[x].ls].siz+tree[tree[x].rs].siz+tree[x].sm;
    return;
}
void lturn(int &x)
{
    int k=tree[x].rs;
    tree[x].rs=tree[k].ls;
    tree[k].ls=x;
    tree[k].siz=tree[x].siz;
    update(x);
    x=k;
    return;
}
void rturn(int &x)
{
    int k=tree[x].ls;
    tree[x].ls=tree[k].rs;
    tree[k].rs=x;
    tree[k].siz=tree[x].siz;
    update(x);
    x=k;
    return;
}
void insert(int &x,int y)
{
    if(!x)
    {
        x=++ps;
        tree[x].sm++;
        tree[x].siz=1;
        tree[x].val=y;
        tree[x].rk=rand()%INF+1;
        return;
    }
    tree[x].siz++;
    if(y<tree[x].val)
        insert(tree[x].ls,y);
    else
        insert(tree[x].rs,y);
    if(tree[x].rs&&tree[x].rk>tree[tree[x].rs].rk)
        lturn(x);
    if(tree[x].ls&&tree[x].rk>tree[tree[x].ls].rk)
        rturn(x);
    update(x);
}
ll get_pre(int x,int y)
{
    if(!x) return -INF;
    if(tree[x].val>=y)
        return get_pre(tree[x].ls,y);
    int k=get_pre(tree[x].rs,y);
    if(!k) return tree[x].val;
    return k;
}
ll get_suf(int x,int y)
{
    if(!x) return INF;
    if(tree[x].val<=y)
        return get_suf(tree[x].rs,y);
    int k=get_suf(tree[x].ls,y);
    if(!k) return tree[x].val;
    return k;
}
ll my_min(ll x,ll y){return x<y?x:y;}
ll my_abs(ll x){return x>0?x:-x;}
signed main()
{
    srand(NULL);
    int x=0;
    n=qreadll();
    x=qreadll();
    insert(root,x);
    ans+=x;
    for(int i=2;i<=n;i++)
    {
        x=qreadll();
        ll pre=get_pre(root,x),suf=get_suf(root,x);
        ans=ans+my_min(my_abs(pre-x),my_abs(suf-x));
        insert(root,x);
    }
    //qpll(ans);
    //putchar('\n');
    cout<<ans<<endl;
    return 0;
}