#define ls root*2
#define rs root*2+1
#define mid (t[root].l+t[root].r)/2
struct node
{
    int nxt,to;
}e[114514*2];
int head[114514*2],cnt1;
void add(int u,int v)
{
    e[++cnt1].to=v;
    e[cnt1].nxt=head[u];
    head[u]=cnt1;
}
//----------????¨º¡Â-------------------
int n,m,a[114514],w[114514]; 
struct node1
{
    int l,r,val,f,coll,colr;
}t[114514*4];
void push_up(int root)
{
	t[root].coll=t[ls].coll,t[root].colr=t[rs].colr;
	t[root].val=t[ls].val+t[rs].val-(t[ls].colr==t[rs].coll);
}
void bld(int l,int r,int root)
{
    t[root].l=l;
    t[root].r=r;
    if(l==r)
    {   
		t[root].coll=w[l];
   		t[root].colr=w[l];
        t[root].val=1;
        return;
    }
    bld(l,mid,ls);
    bld(mid+1,r,rs);
    push_up(root);
}
void down(int root)
{
    t[ls].f=t[rs].f=t[root].f;
    t[ls].coll=t[ls].colr=t[root].f;
    t[rs].coll=t[rs].colr=t[root].f;
    t[ls].val=t[rs].val=1;
    t[root].f=0;
}
void add(int x,int y,int root,int k)
{
    if(t[root].l>=x&&t[root].r<=y)
    {
        t[root].val=1;
        t[root].coll=k,t[root].colr=k;
        t[root].f=k;
        return;
    }
    if(t[root].f)
        down(root);
    if(x<=mid)
        add(x,y,ls,k);
    if(y>mid)
        add(x,y,rs,k);
    push_up(root);
}
int query(int x,int y,int root)
{
    if(t[root].l>=x&&t[root].r<=y)
        return t[root].val;
    if(t[root].f)
        down(root);
	int res=0;
    if(x<=mid)
        res+=query(x,y,ls);
    if(y>mid)
        res+=query(x,y,rs);
    if(t[ls].colr==t[rs].coll) 
		--res;
    return res;
}