水题,找前驱后继即可。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e4+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int d,n,c,son[2],f;}t[N];int cnt,root;
void update(int p){t[p].c=t[t[p].son[0]].c+t[t[p].son[1]].c;}
void add(int d,int f){t[++cnt]=(node){d,1,1,{0,0},f};t[f].son[d>t[f].d]=cnt;}
void rotate(int p,int w)
{
    int f=t[p].f,gf=t[f].f;
    int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
    r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
    r=f;R=p;t[R].son[w]=r;t[r].f=R;update(f),update(p);
}
void splay(int p,int rt)
{
    while(t[p].f!=rt)
    {
        int f=t[p].f,gf=t[f].f;
        if(gf==rt)rotate(p,t[f].son[0]==p);
        else
        {
            if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
            else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
            else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
            else rotate(f,0),rotate(p,0);
        }
    }
    if(!rt)root=p;
}
inline int get_id(int d)
{
    int p=root;
    while(t[p].d!=d)
    {
        if(t[p].d<d)
        {
            if(!t[p].son[1])break;
            p=t[p].son[1];
        }
        else
        {
            if(!t[p].son[0])break;
            p=t[p].son[0];
        }
    }
    return p;
}
void ins(int d)
{
    if(!root){add(d,0);root=1;return ;}
    int p=get_id(d);
    if(t[p].d==d)++t[p].n,update(p),splay(p,0);
    else add(d,p),update(p),splay(cnt,0);
}
void del(int d)
{
    int p=get_id(d);splay(p,0);
    if(t[p].n>1){--t[p].n,update(p);return ;}
    if(!t[p].son[1]&&!t[p].son[0])cnt=0,root=0;
    else if(t[p].son[1]&&!t[p].son[0])root=t[p].son[1],t[root].f=0;
    else if(!t[p].son[1]&&t[p].son[0])root=t[p].son[0],t[root].f=0;
    else
    {
        int R=t[p].son[0];while(t[R].son[1])R=t[R].son[1];splay(R,p);
        int r=t[p].son[1];t[r].f=R;t[R].son[1]=r;root=R;t[root].f=0;
        splay(R,0);
    }
}
int nxt(int d)
{
    int p=get_id(d);splay(p,0);
    if(d>t[p].d&&t[p].son[1])
        for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
    return p;
}
int prv(int d)
{
    int p=get_id(d);splay(p,0);
    if(d<t[p].d&&t[p].son[0])
        for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
    return p;
}
int main()
{
    int n;qr(n);ll ans=0;
    int x;qr(x);
    ins(x);ans=x;
    for(int i=2;i<=n;i++)
    {
        qr(x);
        int pr=prv(x),nx=nxt(x);
        int val=min(abs(t[pr].d-x),abs(t[nx].d-x));
        ans+=val;ins(x);
    }
    qw(ans);puts("");
    return 0;
}

还有一种离线链表做法。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define ll long long 
#define gc getchar()
using namespace std;
const int N=1e5+10;
inline void qr(int &x)
{
    x=0;int f=1;char c=gc;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
struct node{int p,w,nxt,pre;}a[N];int ys[N];
bool cmp(node a,node b){return a.w<b.w;}
int main()
{
    int n;qr(n);
    for(int i=1;i<=n;i++)qr(a[i].w),a[i].p=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)ys[a[i].p]=i,a[i].nxt=i+1,a[i].pre=i-1;
    int l=1,r=n;ll ans=a[ys[1]].w;
    for(int i=n;i>=2;i--)
    {
        int pos=ys[i],pre=a[pos].pre,nxt=a[pos].nxt;
        if(pos==r)r=a[r].pre,ans+=a[pos].w-a[pre].w;
        else if(pos==l)l=a[l].nxt,ans+=a[nxt].w-a[pos].w;
        else ans+=min(a[pos].w-a[pre].w,a[nxt].w-a[pos].w);
        a[nxt].pre=a[pos].pre;
        a[pre].nxt=a[pos].nxt;
    }
    printf("%lld\n",ans);
    return 0;
}