权值分块就是快……Rank5……
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 38001
#define INF 2147483647
#define min(a,b) (((a)<(b))?(a):(b))
struct Point{int v,p;}t[N];
bool operator < (const Point &a,const Point &b){return a.v<b.v;}
int n,ma[N],a[N],en,sum,sz,l[],r[],sumv[],num[N],b[N],ans;
inline void R(int &x){
char c=;int f=;
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');
x*=f;
}
void makeblock()
{
sz=sqrt(en); if(!sz) sz=;
for(sum=;sum*sz<en;sum++)
{
l[sum]=r[sum-]+;
r[sum]=sz*sum;
for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
}
l[sum]=r[sum-]+;
r[sum]=en;
for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
}
inline void Insert(const int &x){b[x]++; sumv[num[x]]++;}
inline int Next(const int &x)
{
if(b[x]>) return x;
for(int i=x+;i<=r[num[x]];i++) if(b[i]) return i;
for(int i=num[x]+;i<=sum;i++) if(sumv[i])
for(int j=l[i];;j++)
if(b[j]) return j;
return INF;
}
inline int Pre(const int &x)
{
if(b[x]>) return x;
for(int i=x-;i>=l[num[x]];i--) if(b[i]) return i;
for(int i=num[x]-;i>=;i--) if(sumv[i])
for(int j=r[i];;j--)
if(b[j]) return j;
return INF;
}
int main()
{
R(n); for(int i=;i<n;i++)
{
R(t[i].v);
t[i].p=i;
}
if(scanf("%d",&t[n].v)==EOF) t[n].v=; t[n].p=n;
sort(t+,t+n+);
ma[a[t[].p]=++en]=t[].v;
for(int i=;i<=n;i++)
{
if(t[i].v!=t[i-].v) en++;
ma[a[t[i].p]=en]=t[i].v;
} makeblock();
Insert(a[]); ans+=ma[a[]];
for(int i=;i<=n;i++)
{
Insert(a[i]);
int Up=Next(a[i]),Down=Pre(a[i]);
if(Up==INF) ans+=(ma[a[i]]-ma[Down]);
else if(Down==INF) ans+=(ma[Up]-ma[a[i]]);
else ans+=min(ma[Up]-ma[a[i]],ma[a[i]]-ma[Down]);
} printf("%d\n",ans);
return ;
}