#include<cstdio>
#include<algorithm>
#define N 100001
using namespace std;
int n,m,a[N],hash[N];
int tot,cnt;
struct node
{
    node * l,* r;
    int sum;
};
node * root[N]; 
inline node * build(node * pre,int l,int r,int w)
{
    node *neww=new node();
    //node * neww=(node *)malloc(sizeof(node));
    neww->sum=pre->sum+1;
    if(l==r) return neww;
    int mid=l+r>>1;
    if(w<=mid)
    {
        neww->r=pre->r;
        neww->l=build(pre->l,l,mid,w);
    }
    else
    {
        neww->l=pre->l;
        neww->r=build(pre->r,mid+1,r,w);
    }
    return neww;
}
node * null(int ll,int rr)
{
    node *neww=new node();
    //node * neww=(node *)malloc(sizeof(node));
    neww->l=neww->r=NULL;
    neww->sum=0;
    if(ll==rr) return neww;
    int mid=ll+rr>>1;
    neww->l=null(ll,mid);
    neww->r=null(mid+1,rr);
    return neww;
}