//By BLADEVIL
#include <cstdio>
#include <set>
#define inf 1<<30 using namespace std; int n,ans; int main()
{
int x;
set<int>bt;
bt.insert(inf); bt.insert(-inf);
scanf("%d",&n);
for (int i=;i<=n;i++)
{
//printf(" %d\n",ans);
if (scanf("%d",&x)==EOF) x=;
if (i==) ans=x,bt.insert(x); else
{
int a,b;
a=*bt.upper_bound(x); b=*(--bt.upper_bound(x));
ans+=(a-x<x-b)?a-x:x-b;
bt.insert(x);
}
}
printf("%d\n",ans);
return ;
}
裸平衡树
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n :longint;
ans :longint;
size, left, right, key :array[..] of longint;
t, tot :longint;
x :longint;
a, b :longint;
i :longint; function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end; procedure left_rotate(var t:longint);
var
k :longint;
begin
k:=right[t];
right[t]:=left[k];
left[k]:=t;
size[k]:=size[t];
size[t]:=size[left[t]]+size[right[t]]+;
t:=k;
end; procedure right_rotate(var t:longint);
var
k :longint;
begin
k:=left[t];
left[t]:=right[k];
right[k]:=t;
size[k]:=size[t];
size[t]:=size[left[t]]+size[right[t]]+;
t:=k;
end; procedure maintain(var t:longint;flag:boolean);
begin
if not flag then
begin
if size[left[left[t]]]>size[right[t]] then
right_rotate(t) else
if size[right[left[t]]]>size[right[t]] then
begin
left_rotate(left[t]);
right_rotate(t);
end else exit;
end else
begin
if size[right[right[t]]]>size[left[t]] then
left_rotate(t) else
if size[left[right[t]]]>size[left[t]] then
begin
right_rotate(right[t]);
left_rotate(t);
end else exit;
end;
maintain(left[t],false);
maintain(right[t],true);
maintain(t,true);
maintain(t,false);
end; procedure insert(var t:longint;v:longint);
begin
if t= then
begin
inc(tot);
t:=tot;
left[t]:=;
right[t]:=;
size[t]:=;
key[t]:=v;
end else
begin
inc(size[t]);
if v<key[t] then insert(left[t],v) else insert(right[t],v);
maintain(t,v>=key[t]);
end;
end; function pred(var t:longint;v:longint):longint;
begin
if t= then exit(-);
if key[t]>v then pred:=pred(left[t],v) else
begin
pred:=pred(right[t],v);
if pred=- then pred:=key[t];
end;
end; function succ(var t:longint;v:longint):longint;
begin
if t= then exit(-);
if key[t]<v then succ:=succ(right[t],v) else
begin
succ:=succ(left[t],v);
if succ=- then succ:=key[t];
end;
end; begin
read(n);
t:=; tot:=;
read(x);
ans:=x;
insert(t,x);
for i:= to n do
begin
read(x);
a:=pred(t,x); b:=succ(t,x);
if a=- then inc(ans,b-x) else
if b=- then inc(ans,x-a) else
ans:=ans+min(abs(a-x),abs(b-x));
insert(t,x);
end;
writeln(ans);
end.