1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=1e5,inf=(1ll<<31)-1;
ll bufch[2][N+5],bufval[N+5],bufsiz[N+5],bufrnd[N+5];
ll *nowch[2]={bufch[0],bufch[1]},*nowval=bufval,*nowsiz=bufsiz
,*nowrnd=bufrnd;
struct Fhq_Treap{
ll *ch[2],*val,*siz,*rnd;ll rt,sz;
inline void Init(ll x) {
x+=5;ch[0]=nowch[0];ch[1]=nowch[1];val=nowval;siz=nowsiz;rnd=nowrnd;
nowch[0]+=x;nowch[1]+=x;nowval+=x;nowsiz+=x;nowrnd+=x;
}
inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
inline void Clear(ll x) {ch[0][x]=ch[1][x]=val[x]=siz[x]=rnd[x]=0;}
inline void Split(ll p,ll k,ll &x,ll &y) {
if(!p) {x=y=0;return;}
if(val[p]<=k) {x=p;Split(ch[1][p],k,ch[1][p],y);}
else {y=p;Split(ch[0][p],k,x,ch[0][p]);}Pushup(p);
}
inline ll Merge(ll x,ll y) {
if(!x||!y) return x|y;
if(rnd[x]<rnd[y]) {ch[0][y]=Merge(x,ch[0][y]);Pushup(y);return y;}
else {ch[1][x]=Merge(ch[1][x],y);Pushup(x);return x;}
}
inline ll Find(ll k) {
if(!rt) return 0;ll cur=rt;
while(ch[k>val[cur]][cur]&&k!=val[cur]) cur=ch[k>val[cur]][cur];
return cur;
}
inline void Ins(ll k) {
val[++sz]=k;siz[sz]=1;rnd[sz]=rand();
if(!rt) {rt=sz;return;}
ll x,y;Split(rt,k,x,y);rt=Merge(Merge(x,sz),y);
}
inline ll Rk(ll k) {
ll x,y,r;Split(rt,k-1,x,y);r=siz[x]+1;rt=Merge(x,y);return r;
}
inline ll Kth(ll k) {
ll cur=rt;
while(1) {
if(ch[0][cur]&&k<=siz[ch[0][cur]]) cur=ch[0][cur];
else {k-=siz[ch[0][cur]]+1;if(k<=0) return val[cur];cur=ch[1][cur];}
}
}
inline ll Pre(ll k) {return Kth(Rk(k)-1);}
inline ll Nxt(ll k) {return Kth(Rk(k+1));}
}t;
int main() {
srand(73939133);ll n;n=read();t.Init(n+2);t.Ins(inf);t.Ins(-inf);
ll ans=read();t.Ins(ans);
for(ll i=2;i<=n;i++) {
ll x,tmp1,tmp2,tmp3;x=read();
tmp1=t.Pre(x);tmp2=t.Nxt(x);tmp3=t.val[t.Find(x)];
ans+=min(abs(x-tmp1),min(abs(x-tmp2),abs(x-tmp3)));
t.Ins(x);
}
write(ans);
return 0;
}
|