#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 50007#define inf 0x7fffffffusing namespace std;int n,a[N],d[N],ans;struct Data{    int x,ord;}data[N];struct tree{    int l,r,mn,mx,sum;}tr[N<<2];bool cmp(Data a,Data b){return a.x<b.x;}void build(int now,int l,int r){    tr[now].l=l;tr[now].r=r;tr[now].mn=inf-1;tr[now].mx=-1;    if(l==r) return;    int mid=(l+r)>>1;    build(now<<1,l,mid);build(now<<1|1,mid+1,r);}inline void push_up(int now){    tr[now].sum=tr[now<<1].sum+tr[now<<1|1].sum;    tr[now].mx=max(tr[now<<1].mx,tr[now<<1|1].mx);    tr[now].mn=min(tr[now<<1].mn,tr[now<<1|1].mn);}void modify(int now,int x){    if(tr[now].l==tr[now].r && tr[now].l==x)    {        tr[now].sum=1;        tr[now].mx=x;        tr[now].mn=x;        return;    }    int mid=(tr[now].l+tr[now].r)>>1;    if(x>mid) modify(now<<1|1,x);    if(x<=mid)modify(now<<1,x);    push_up(now);}int querymx(int now,int l,int r){    if(r<l) return -1;    if(tr[now].sum==0) return -1;    if(tr[now].l==l&&tr[now].r==r) return tr[now].mx;    int mid=(tr[now].l+tr[now].r)>>1;    if(r<=mid) return querymx(now<<1,l,r);    else if(l>mid) return querymx(now<<1|1,l,r);    else return max(querymx(now<<1,l,mid),querymx(now<<1|1,mid+1,r));}int querymn(int now,int l,int r){    if(r<l) return -1;    if(tr[now].sum==0) return inf-1;    if(tr[now].l==l&&tr[now].r==r) return tr[now].mn;    int mid=(tr[now].l+tr[now].r)>>1;    if(r<=mid) return querymn(now<<1,l,r);    else if(l>mid) return querymn(now<<1|1,l,r);    else return min(querymn(now<<1,l,mid),querymn(now<<1|1,mid+1,r));}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        if(scanf("%d",&a[i])==EOF) a[i]=0;        data[i].ord=i;data[i].x=a[i];    }    sort(data+1,data+n+1,cmp);    int ord=1;d[1]=data[1].x;a[data[1].ord]=ord;    for(int i=2;i<=n;i++)    {        if(data[i].x!=data[i-1].x) ord++;        a[data[i].ord]=ord;d[ord]=data[i].x;    }    build(1,1,ord);    ans=d[a[1]];modify(1,a[1]);    for(int i=2;i<=n;i++)    {        int x=querymx(1,1,a[i]-1),y=querymn(1,a[i],n),tmp=inf;        if(x!=-1) tmp=min(tmp,d[a[i]]-d[x]);        if(y!=inf-1) tmp=min(tmp,d[y]-d[a[i]]);        ans+=tmp;        modify(1,a[i]);    }    printf("%d\n",ans);    return 0;}

#include<cstdio>#include<algorithm>#include<map>#define N 50010#define inf 0x7fffffffusing namespace std;int n,a[N],d[N];struct Data{    int x,ord;}data[N];bool cmp(Data a,Data b){    return a.x<b.x;}struct node{    int l,r,sum,mx,mn;}t[N<<2];void pushup(int rt){    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;    t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);    t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);}void build(int rt,int l,int r){    t[rt].l=l;t[rt].r=r;t[rt].mx=-1;t[rt].mn=inf-1;    if(l==r) return;    int mid=(l+r)>>1;    if(l<=mid) build(rt<<1,l,mid);    if(r>mid) build(rt<<1|1,mid+1,r);}void modify(int rt,int pos){    if(t[rt].l==t[rt].r){        t[rt].sum=1;        t[rt].mn=t[rt].l;        t[rt].mx=t[rt].l;        return;    }    int mid=(t[rt].l+t[rt].r)>>1;    if(pos<=mid) modify(rt<<1,pos);    if(pos>mid) modify(rt<<1|1,pos);    pushup(rt);}int querymx(int rt,int l,int r){    if(r<l) return -1;    if(t[rt].sum==0) return -1;    if(l<=t[rt].l&&t[rt].r<=r) return t[rt].mx;    int mid=(t[rt].l+t[rt].r)>>1,ret=-2;    if(l<=mid) ret=max(ret,querymx(rt<<1,l,r));    if(r>mid) ret=max(ret,querymx(rt<<1|1,l,r));    return ret;}int querymn(int rt,int l,int r){    if(r<l) return inf-1;    if(t[rt].sum==0) return inf-1;    if(l<=t[rt].l&&t[rt].r<=r) return t[rt].mn;    int mid=(t[rt].l+t[rt].r)>>1,ret=inf;    if(l<=mid) ret=min(ret,querymn(rt<<1,l,r));    if(r>mid) ret=min(ret,querymn(rt<<1|1,l,r));    return ret;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        if(scanf("%d",&a[i])==EOF) a[i]=0;        data[i].ord=i;data[i].x=a[i];    }    sort(data+1,data+1+n,cmp);    int ord=1;d[1]=data[1].x;a[data[1].ord]=ord;    for(int i=2;i<=n;i++){        if(data[i].x!=data[i-1].x) ord++;        a[data[i].ord]=ord;d[ord]=data[i].x;    }    build(1,1,ord);    int ans=d[a[1]];modify(1,a[1]);    for(int i=2;i<=n;i++){        int x=querymx(1,1,a[i]-1),y=querymn(1,a[i],n),tmp=inf;        if(x!=-1) tmp=min(tmp,d[a[i]]-d[x]);        if(y!=inf-1) tmp=min(tmp,d[y]-d[a[i]]);        ans+=tmp;        modify(1,a[i]);    }    printf("%d\n",ans);    return 0;}