rt，样例过了，WA on #1

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

namespace io
{
	inline int read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
	template<typename T>inline void write(T x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
}
using namespace io;

const int M=1e6;
int n,m,a[M],cnt[M],bl[M],sz,now,ans[M];
struct qry{int l,r,id;}q[M];
bool cmp(qry a,qry b){return(bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:((bl[a.l]&1)?a.r<b.r:a.r>b.r);}

void add(int x)
{
    cnt[a[x]]++;
    if(cnt[a[x]]%2==0) now++;
}

void del(int x)
{
    if(cnt[a[x]]%2==0) now--;
    cnt[a[x]]--;
}

signed main()
{
	n=read();
    sz=sqrt(n);
    for(int i=1;i<=ceil((double)n/sz);i++)for(int j=(i-1)*sz+1;j<=i*sz;j++)bl[j]=i;
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();
    for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0;i<=m;i++)
    {
        int ql=q[i].l,qr=q[i].r;
        while(l<ql) del(l++);
        while(l>ql) add(--l);
        while(r<qr) add(++r);
        while(r>qr) del(r--);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}