【题解】
treap模板题，直接用Treap维护前驱、后继，每次找到更接近当前val的加上就好了。
#include<cstdio>
#include<algorithm>
#define ls (a[u].l)
#define rs (a[u].r)
#define LL long long
using namespace std;
const int maxn=;
int n,k,x,y,z,v,tot,root;
struct treap{int l,r,v,rnd,size;}a[maxn];
LL sum=;
inline void read(int &k){
k=; int f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
k*=f;
}
void newnode(int v){a[++tot]=(treap){,,v,rand()+,};}
void update(int u){a[u].size=a[ls].size+a[rs].size+;}
void split(int u,int k,int &x,int &y){
if(!k){x=; y=u; return;}
if(a[u].size==k){x=u; y=; return;}
if(a[ls].size>=k) split(ls,k,x,ls),y=u;
else split(rs,k-a[ls].size-,rs,y),x=u;
update(u);
}
int merge(int x,int y){
if(!(x*y)) return x+y;
if(a[x].rnd>a[y].rnd){
a[y].l=merge(x,a[y].l); update(y); return y;
}
else{
a[x].r=merge(a[x].r,y); update(x); return x;
}
}
int qrank(int u,int val){
if(!u) return ;
if(a[u].v>=val) return qrank(ls,val);
return qrank(rs,val)+a[ls].size+;
}
int qval(int u,int k){
if(a[ls].size+==k) return a[u].v;
return a[ls].size>=k?qval(ls,k):qval(rs,k-a[ls].size-);
}
int main(){
srand(); root=tot=; a[root].v=2e9; a[root].size=;
read(n);
for(int i=;i<=n;i++){
read(v);
if(i<=) sum+=abs(v-sum);
else{
int tmp=qrank(root,v),ans=0X7f7f7f;
if(tmp) ans=abs(v-qval(root,tmp));
if(tmp<a[root].size) ans=min(ans,abs(v-qval(root,tmp+)));
sum+=ans;
}
split(root,qrank(root,v),x,y);
newnode(v); root=merge(merge(x,tot),y);
}
return printf("%lld",sum),;
}