莫队60pts求卡常

#include<bits/stdc++.h>
#define rep(i,n,m) for(int i=(n);i<=(m);++i)
#define ref(i,n,m) for(int i=(n);i>=(m);--i)
namespace Fast{
    namespace Fread{const int SIZE=1<<20;char buf[SIZE],*S,*TT;inline char getchar(){if(S==TT){TT=(S=buf)+fread(buf,1,SIZE,stdin);if(S==TT)return '\n';}return *S++;}}
    namespace Fwrite{const int SIZE=1<<20;char buf[SIZE],*S=buf,*TT=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==TT)flush();}struct NTR{~NTR(){flush();}} ztr;}
    using namespace Fread;
    using namespace Fwrite;
    #define getchar Fread::getchar
    #define putchar Fwrite::putchar
    namespace FastIO{
        struct Reader{
            template <typename T>
            Reader &operator>>(T &from){from=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')from=(from<<3)+(from<<1)+(c^48),c=getchar();from*=f;return *this;}
            Reader &operator>>(double &from){from=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')from=from*10+(c^48),c=getchar();if(c=='.')c=getchar();else{from*=f;return *this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;from=(from+t)*f;return *this;}
            Reader &operator>>(long double &from){from=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')from=from*10+(c^48),c=getchar();if(c=='.')c=getchar();else{from*=f;return *this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;from=(from+t)*f;return *this;}
            Reader &operator>>(__float128 &from){from=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')from=from*10+(c^48),c=getchar();if(c=='.')c=getchar();else{from*=f;return *this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;from=(from+t)*f;return *this;}
            Reader &operator>>(char &c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return *this;}
            Reader &operator>>(char *str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
            Reader(){}
        }cin;
        struct Writer{
            const int Setprecision=6;
            typedef int mxdouble;
            template <typename T>
            Writer &operator<<(T from){if(from==0){putchar('0');return *this;}if(from<0)putchar('-'),from=-from;static short sta[40];short top=0;while(from>0)sta[++top]=from%10,from/=10;while(top>0)putchar(sta[top]+'0'),top--;return *this;}
            Writer &operator<<(double from){if(from<0)putchar('-'),from=-from;mxdouble _=from;from-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)from*=10;_=from;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return *this;}
            Writer &operator<<(long double from){if(from<0)putchar('-'),from=-from;mxdouble _=from;from-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)from*=10;_=from;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return *this;}
            Writer &operator<<(__float128 from){if(from<0)putchar('-'),from=-from;mxdouble _=from;from-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)from*=10;_=from;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return *this;}
            Writer &operator<<(char c){putchar(c);return *this;}
            Writer &operator<<(char *str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
            Writer &operator<<(const char *str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
            Writer() {}
        } cout;
        inline int qpow(register const int e,register const int b){if(!b) return 1;if(b==1) return e;int res=qpow(e,b>>1);if(b&1) return res*res*e;return res*res;}
        inline int power(register const int e,register const int b,register const int mod){if(!b) return 1;if(b==1) return e;register int res=power(e,b>>1,mod)%mod;if(b&1) return res%mod*res%mod*e%mod;return res%mod*res%mod;}
    }
    int max(register const int e, register const int b){register const int from(e),to(b);return (from>to?from:to);}
    int min(register const int e, register const int b){register const int from(e),to(b);return (from>to?to:from);}
}
using namespace Fast;
#define cin FastIO::cin
#define cout FastIO::cout
using namespace std;
static const int N=1e6+5;
int n,m,B,reid,l=1,r=0,ans=0;
int a[N]__attribute__((aligned(64))),pos[N]__attribute__((aligned(64))),belongs[N]__attribute__((aligned(64))),tot[N]__attribute__((aligned(64))),res[N]__attribute__((aligned(64)));
struct Query{
    int l,r,id;
}q[N]__attribute__((aligned(64)));
bool cmp(const Query&A,const Query&B){
    if(pos[A.l]!=pos[B.l]) return pos[A.l]<pos[B.l];
    return (pos[A.l]&1)^(A.r<B.r);
}
signed main(){
    cin>>n;
    B=sqrt(n);
    rep(i,1,n){
        int x;
        cin>>x;
		a[i]=x;
        pos[i]=(i-1)/B+1;
    }
    cin>>m;
    rep(i,1,m) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
	rep(i,1,m){
    	while(l<q[i].l){
    		ans-=(--tot[a[l++]]==0?1:0);
		}
    	while(l>q[i].l){
    		ans+=(++tot[a[--l]]==1?1:0);
		}
    	while(r<q[i].r){
    		ans+=(++tot[a[++r]]==1?1:0);
		}
    	while(r>q[i].r){
    		ans-=(--tot[a[r--]]==0?1:0);
		}
		res[q[i].id]=ans;
	}
	rep(i,1,m) cout<<res[i]<<"\n";
    return 0;
}