就是个二叉搜索树的水题……让我用$Splay$给过了……

不过以后需要注意的一点是，在找前驱后继的时候,对于这个题一定要是下标不为$0$,而不是权值不为$0$,因为是可以有负数的。

(*￣m￣)我就因为这个一直$90$分……也不知道为什么数据这么水$qwq$

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000007
int f[MAXN],cnt[MAXN],value[MAXN],sons[MAXN][2],sub_size[MAXN],whole_size,root;                 
inline void S_Clear(int x){
    sons[x][0]=sons[x][1]=f[x]=sub_size[x]=cnt[x]=value[x]=0; 
    return ;
}
inline bool get_which(int x){
    return sons[f[x]][1]==x;
}
inline void update(int x){
     sub_size[x]=cnt[x];  
     if (sons[x][0]) sub_size[x]+=sub_size[sons[x][0]];  
     if (sons[x][1]) sub_size[x]+=sub_size[sons[x][1]];  
     return ;
}
inline void rotate(int x){
    int father=f[x],g_father=f[father],which_son=get_which(x);
    sons[father][which_son]=sons[x][!which_son];
    f[sons[father][which_son]]=father;
    sons[x][!which_son]=father;
    f[father]=x;
    f[x]=g_father;
    if(g_father){
        sons[g_father][sons[g_father][1]==father]=x;
    }
    update(father);
    update(x);
    return ;
}
inline void splay(int x){
    for (int fa;fa=f[x];rotate(x))  
      if (f[fa])  
        rotate((get_which(x)==get_which(fa))?fa:x);  
    root=x;  
    return ;
}
inline void insert(int x){
    if(!root){
        whole_size++;
        sons[whole_size][0]=sons[whole_size][1]=f[whole_size]=0;
        root=whole_size;
        sub_size[whole_size]=cnt[whole_size]++;
        value[whole_size]=x;
        return ;
    } 
    int now=root,fa=0;
    while(1){
        if(x==value[now]){
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            break;
        }
        fa=now;
        now=sons[now][value[now]<x];
        if(!now){
            whole_size++;
            sons[whole_size][0]=sons[whole_size][1]=0;
            f[whole_size]=fa;
            sub_size[whole_size]=cnt[whole_size]=1;
            sons[fa][value[fa]<x]=whole_size;
            value[whole_size]=x;
            update(fa);
            splay(whole_size);
            break; 
        }
    }
    return ;
}
inline int find_pre(){
    int now=sons[root][0];
    if(!now)return now;
    while(sons[now][1])now=sons[now][1];
    return now;
}
inline int find_suffix(){
    int now=sons[root][1];
    if(!now)return now;
    while(sons[now][0])now=sons[now][0];
    return now;
}
inline int abs(int n){
    return n>=0?n:-n;
}
int main(){
    int n,a;
    cin>>n;
    cin>>a;
    insert(a);
    int sum=a;
    for(int i=2;i<=n;i++){
        cin>>a;
        insert(a);
        if(cnt[root]>=2)continue;
        int pre=find_pre(),minn=90909090;
        int suffix=find_suffix();
        if(pre)minn=min(abs(value[pre]-a),minn);
        if(suffix)minn=min(abs(value[suffix]-a),minn);
        sum+=minn;
    }
    cout<<sum;
    return 0;
}