最近各种瞎写数论题，感觉需要回顾一下数据结构
写一发splay冷静一下（手速过慢，以后要多练练）
用splay是最直接的方法，但我感觉离散一波应该可以做出来（没仔细想过）
现在没有很追求代码优美，感觉得先打的对打的快O(∩_∩)O
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
int root,N,n,x;
int fa[],c[][],a[];
void rot(int x)
{
int fat=fa[x],k=c[fat][]==x;
c[fat][k]=c[x][!k];fa[c[x][!k]]=fat;
fa[x]=fa[fat];c[fa[fat]][c[fa[fat]][]==fat]=x;
fa[fat]=x;c[x][!k]=fat;
}
void splay(int x,int g)
{
for(int y;(y=fa[x])!=g;rot(x))
if(fa[y]!=g)
if((c[y][]==x)==(c[fa[y]][]==y)) rot(y);else rot(x);
if(g==) root=x;
}
int lower(int p)
{
if(!root) return ;
int ans=INF;
for(int i=root;i;(p>=a[i])?i=c[i][]:i=c[i][])
if(a[i]>=p)
ans=min(ans,a[i]);
return ans-p;
}
int upper(int p)
{
if(!root) return ;
int ans=-INF;
for(int i=root;i;(p>=a[i])?i=c[i][]:i=c[i][])
if(a[i]<=p)
ans=max(ans,a[i]);
return p-ans;
}
void add(int x)
{
a[++N]=x;c[N][]=c[N][]=;
if(!root)
{
root=N;
return;
}
for(int i=root;;)
if(x<=a[i])
if(!c[i][])
{
c[i][]=N,fa[N]=i;
splay(N,);
break;
}
else i=c[i][];
else
if(!c[i][])
{
c[i][]=N,fa[N]=i;
splay(N,);
break;
}
else i=c[i][];
}
int main()
{
scanf("%d",&n);int ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
if(i==) ans+=x;
else
ans+=min(upper(x),lower(x));
add(x);
}
printf("%d\n",ans);
return ;
}