这道题还是Treap查找前驱/后继。

与这题不同的地方在于这题的前驱和后继是可以等于其原数的。。。

开始我还以为只要每次查询之前的最小值，搞个堆就好了。。。

#include 
    
     const int inf=0x3f3f3f3f;int N,Ans;struct Treap{    Treap *ch[2];    int size,cnt,r,v;    Treap(int x)    {        size=cnt=1;        r=rand();        v=x;        ch[0]=ch[1]=NULL;    }    int cmp(int x)    {        if(x==v) return -1;        return x>v;    }    void maintain()    {        size=cnt+((ch[0]==NULL)?0:ch[0]->size)+((ch[1]==NULL)?0:ch[1]->size);    }}*root;void rotate(Treap* &o,int d){    Treap *k=o->ch[d^1];    o->ch[d^1]=k->ch[d];    k->ch[d]=o;    o->maintain(),k->maintain();    o=k;}void insert(Treap* &o,int x){    if(o==NULL) o=new Treap(x);    else    {        if(o->v==x) ++(o->cnt);        else        {            int d=o->cmp(x);            insert(o->ch[d],x);            if(o->ch[d]->r>o->r) rotate(o,d^1);        }    }    o->maintain();}int upper(Treap *o,int x){    if(o==NULL) return -inf;    if(o->v>x) return upper(o->ch[0],x);    else return std::max(o->v,upper(o->ch[1],x));}int lower(Treap *o,int x){    if(o==NULL) return inf;    if(o->v
     
      ch[1],x);    else return std::min(o->v,lower(o->ch[0],x));}inline int read(){    register int x=0,v=1;    register char ch=getchar();    while(!isdigit(ch))    {        if(ch=='-') v=-1;        ch=getchar();    }    while(isdigit(ch))    {        x=(x<<1)+(x<<3)+ch-'0';        ch=getchar();    }    return x*v;}int main(){    int t;    N=read();    for(register int i=1;i<=N;++i)    {        t=read();        if(root==NULL) Ans+=t;        else Ans+=std::min(lower(root,t)-t,t-upper(root,t));        insert(root,t);    }    printf("%d\n",Ans);    return 0;}