# 2. 题解

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct N{LL d,f,s;N*l,*r;N();}*def=new N;
N::N(){d=f=s=0;l=r=def;}
struct treap
{
N*root;
treap(){root=def;}
void update(N*&a){a->s=a->l->s+a->r->s+1;}
void lrot(N*&a){N*b=a->r;a->r=b->l,b->l=a,b->s=a->s,update(a),a=b;}
void rrot(N*&a){N*b=a->l;a->l=b->r,b->r=a,b->s=a->s,update(a),a=b;}
void insert(N*&a,LL data)
{
if(a==def)
{
a=new N;
a->d=data,a->f=rand(),a->s=1;
return;
}
if(data<a->d){if(insert(a->l,data),a->l->f<a->f)rrot(a);}
else if(data>a->d)if(insert(a->r,data),a->r->f<a->f)lrot(a);
update(a);
}
LL pre(N*&a,LL data)
{
if(a==def)return (LL)-1e8;
if(a->d==data)return a->d;
if(a->d<data)return max(a->d,pre(a->r,data));
return pre(a->l,data);
}
LL nxt(N*&a,LL data)
{
if(a==def)return (LL)1e8;
if(a->d==data)return a->d;
if(a->d>data)return min(a->d,nxt(a->l,data));
return nxt(a->r,data);
}
}t;
template<typename _Tp>void IN(_Tp&dig)
{
char c=getchar();bool flag=0;dig=0;
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')flag=1,c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
if(flag)dig=-dig;
}
LL n,ans;
int main()
{
IN(n),IN(ans),t.insert(t.root,ans),srand(n);
for(LL i=2,a,pre,nxt;i<=n;i++)
IN(a),ans+=min(a-t.pre(t.root,a),t.nxt(t.root,a)-a),t.insert(t.root,a);
printf("%lld\n",ans);
return 0;
}


# markdown

markdown 当然会吃 “<“

set