TLE TLE TLE......

kth肯定有问题，但是有啥问题呢？

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int cnt,root;

struct node{
    int ls,rs;
    int key;
    int pri,size;
}t[N];

void newNode(int x)
{
    cnt++;
    t[cnt].key=x;
    t[cnt].pri=rand();
    t[cnt].size=1;
}

void Update(int x)
{
    t[x].size=t[t[x].ls].size+t[t[x].rs].size+1;
}

void Split(int u,int x,int &L,int &R)
{
    if(u==0) { L=R=0; return; }
    if(t[u].key<=x) { L=u; Split(t[u].rs,x,t[u].rs,R); }
    else { R=u; Split(t[u].ls,x,L,t[u].ls); }
    Update(u);
}

int Merge(int L,int R)
{
    if(L==0 || R==0) return L+R;
    if(t[L].pri>t[R].pri) { t[L].rs=Merge(t[L].rs,R); Update(L); return L; }
    else { t[R].ls=Merge(L,t[R].ls); Update(R); return R; }
}

void Insert(int x)
{
    int L,R;
    Split(root,x,L,R);
    newNode(x);
    root=Merge(Merge(L,cnt),R);
}

int kth(int u,int k)
{
    if(k==t[t[u].ls].size+1) return t[u].key;
    if(k<=t[t[u].ls].size) return kth(t[u].ls,k);
    if(k>t[t[u].ls].size) return kth(t[u].rs,k-t[t[u].ls].size-1);
}

int Pre(int x)
{
    int L,R,res;
    Split(root,x-1,L,R);
    res=kth(L,t[L].size);
    root=Merge(L,R);
    return res;
}

int Suc(int x)
{
    int L,R,res;
    Split(root,x,L,R);
    res=kth(R,1);
    root=Merge(L,R);
    return res;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(time(0));
    int n,ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        Insert(x);
        ans+=min(x-Pre(x),Suc(x)-x);
    }
    cout<<ans;

    return 0;
}