#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
#define inf 0x7f7f7f7f
const int N=5005;
int a[5005];
struct node
{
int lft,rht;
int sum;
int mid()
{
return MID(lft,rht);
}
}; struct Segtree
{
node tree[N*4];
void build(int lft,int rht,int rt)
{
tree[rt].lft=lft;
tree[rt].rht=rht;
tree[rt].sum=0;
if(lft!=rht)
{
int mid=tree[rt].mid();
build(lft,mid,LL(rt));
build(mid+1,rht,RR(rt));
tree[rt].sum=tree[LL(rt)].sum+tree[RR(rt)].sum;
}
}
void updata(int pos,int rt)
{
if(tree[rt].lft==tree[rt].rht)
tree[rt].sum++;
else
{
int mid=tree[rt].mid();
if(pos<=mid)
updata(pos,LL(rt));
else
updata(pos,RR(rt));
tree[rt].sum=tree[LL(rt)].sum+tree[RR(rt)].sum;
}
}
int query(int st,int ed,int rt)
{
int lft=tree[rt].lft,rht=tree[rt].rht;
if(st<=lft&&rht<=ed){
return tree[rt].sum;
}
else
{
int mid=tree[rt].mid();
int sum1=0,sum2=0;
if(st<=mid)
sum1=query(st,ed,LL(rt));
if(ed>mid)
sum2=query(st,ed,RR(rt));
return sum1+sum2;
}
}
}seg;