1 #include <cstdio> 2 #include <cstdlib> 3 #include <ctime> 4 using namespace std; 5 const int inf=10000000; 6 struct node{ 7     int val,weight; 8     node *ch[2]; 9     node (int key) {10         val=key;weight=rand();11         ch[0]=ch[1]=NULL;12     }13 }*root;14 int n,ans;15 void rotate(node *&t,int d){16     node *c=t->ch[d];17     t->ch[d]=c->ch[!d];18     c->ch[!d]=t;19     t=c;20 }21 bool find (node *t,int key){22     while (t!=NULL) {23         if (t->val==key) return 1;24         t=t->ch[key>(t->val)];25     }26     return 0;    27 }28 int pred (node *t,int key){29     int ret=-inf;30     while (t!=NULL) {31         if (t->val<key) {if (t->val>ret) ret=t->val;t=t->ch[1];} else 32             t=t->ch[0];33     }34     return ret;35 }36 int succ (node *t,int key){37     int ret=inf;38     while (t!=NULL) {39         if (t->val>key) {if (t->val<ret) ret=t->val;t=t->ch[0];} else 40             t=t->ch[1];    41     }42     return ret;43 }44 void insert (node *&t,int key){45     if (t==NULL) {46         t=new node(key);return ;47     }    48     int d=key>t->val;49     insert(t->ch[d],key);50     if (t->ch[d]->weight>t->weight) rotate(t,d);51 }52 int main(){53     ans=0;54     srand(19961111);55     scanf("%d",&n);56     int x,x1,x2;57     scanf("%d",&x);ans+=x;58     root=new node(x);59     for (int i=2;i<=n;i++){60         if (scanf("%d",&x)==EOF) x=0;61         if (!find(root,x)) {62             x1=pred(root,x);x2=succ(root,x);63             ans+=(x2-x<x-x1)?x2-x:x-x1;64             insert(root,x);65         }66     }67     printf("%d\n",ans);68     return 0;69 }