比暴力还差，跟shit一样

#include<bits/stdc++.h>
using namespace std;
struct node
    {
    int ls,rs,v;
    }a[32768];
long long n,ans=0,cnt=0,z[100005],l=0,r=0;
inline int read() 
    {
    int num=0,w=1; char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar(); }
    while(ch>='0'&&ch<='9') num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return num*w;
    }
int ins(int pre,int x,int v,int op,int minn,int q)
    {
    if(!x)
        {
        if(op&1){a[pre].ls=cnt;a[cnt].v=v;}
        else {a[pre].rs=cnt;a[cnt].v=v;}
        return min(minn,abs(a[pre].v-v));
        }
    minn=min(minn,abs(v-a[x].v));
    if(v<a[x].v)
        {
        if(pre==0 && q==0)l++;
        return ins(x,a[x].ls,v,1,minn,1);
        }
    else 
        {
        if(pre==0 && q==0)r++;
        return ins(x,a[x].rs,v,2,minn,1);
        }
    }
void rebuild()
    {
    int pcnt=cnt;cnt=1;
    int pn=pcnt>>1;
    for(int i=1;i<=pcnt;i++)a[i].ls=a[i].rs=a[i].v=0;
    a[1].v=z[pn];
    for(int i=1;i<pn;i++)
        {
        cnt++;
        ins(0,1,z[i],0,2e9,1);
        }
    for(int i=pn+1;i<=pcnt;i++)
        {
        cnt++;
        ins(0,1,z[i],0,2e9,1);
        }
    cnt=pcnt;int q=(l+r)>>1;l=q;r=q;
    if((l+r)&1)r++;
    }
signed main()
    {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
	for(int i=1;i<=n;i++)z[i]=read();
    for(int i=1;i<=n;i++)
        {
        int x=z[i];cnt++;
        if(i==1){a[i].v=x;ans+=x;}
        else ans+=ins(0,1,x,0,2e9,0);	
        if(l>=0.9*cnt||r>=0.9*cnt)rebuild();
        }
    cout<<ans;
    return 0;
    }
/*
10
1 1 2 3 4 5 3 4 1 3
*/