struct k_segment{
    int t[N],size;

    inline void update(int rt,int num,int l,int r,int v){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(l==r){t[rt]+=v;return;}
    
        if(num<=mid) update(lc,num,l,mid,v);
        else update(rc,num,mid+1,r,v);

        t[rt]=t[lc]+t[rc];
    }

    inline int queryK(int rt,int l,int r,int rk){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(l==r) return l;

        if(t[lc]>=rk) return queryK(lc,l,mid,rk);
        else return queryK(rc,mid+1,r,rk-t[lc]);
    }

    inline int query(int rt,int l,int r,int ql,int qr){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(ql<=l&&r<=qr) return t[rt];

        int ans=0;

        if(ql<=mid) ans+=query(lc,l,mid,ql,qr);
        if(qr>mid) ans+=query(rc,mid+1,r,ql,qr);

        return ans;
    }

    inline int rank(int x){
        if(x<=1) return 1;
        return query(1,1,size,1,x-1)+1;
    }

    inline int find_pre(int rt,int l,int r){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;
        
        if(l==r) return l;

        if(t[rc]) return find_pre(rc,mid+1,r);

        return find_pre(lc,l,mid);
    }

    inline int pre(int rt,int l,int r,int num){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(r<num){
            if(t[rt]) return find_pre(rt,l,r);
            return 0;
        }

        int ans=0;

        if(mid<num-1&&t[rc]&&(ans=pre(rc,mid+1,r,num))) return ans;

        return pre(lc,l,mid,num);
    }

    inline int find_next(int rt,int l,int r){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(l==r) return l;

        if(t[lc]) return find_next(lc,l,mid);
        
        return find_next(rc,mid+1,r);
    }

    inline int next(int rt,int l,int r,int num){
        int lc=rt<<1,rc=rt<<1|1,mid=(l+r)>>1;

        if(num<l){
            if(t[rt]) return find_next(rt,l,r);
            return 0;
        }

        int ans=0;

        if(num<mid&&t[lc]&&(ans=next(lc,l,mid,num))) return ans;

        return next(rc,mid+1,r,num);
    }
}a;