卡常玄关

#include<bits/stdc++.h>
#define il inline
#define rg register
using namespace std;
namespace FastIO
{
    const int BUFFER_SIZE=1<<20;
    char input[BUFFER_SIZE],output[BUFFER_SIZE];
    int input_pos=0,input_len=0,output_pos=0;
    il void read_buffer()
	{
        input_len=fread(input,1,BUFFER_SIZE,stdin);
        input_pos=0;
    }
    il char get_char()
	{
        if(input_pos>=input_len)read_buffer();
        return input[input_pos++];
    }
    il int read_int()
	{
        char c=get_char();
        while(c<=' ')
        {
        	c=get_char();
		}
        int x=0;
        while(c>='0'&&c<='9')
		{
            x=x*10+c-'0';
            c=get_char();
        }
        return x;
    }
    il void write_int(int x)
	{
        if(x<0)
		{
            output[output_pos++]='-';
            x=-x;
        }
        char buffer[12];
        int len=0;
        do
		{
            buffer[len++]='0'+x%10;
            x/=10;
        }while(x);
        while(len--)
		{
            output[output_pos++]=buffer[len];
        }
        output[output_pos++]='\n';
        if(output_pos>=BUFFER_SIZE-20)
		{
            fwrite(output,1,output_pos,stdout);
            output_pos=0;
        }
    }
    il void flush()
	{
        if(output_pos>0)
		{
            fwrite(output,1,output_pos,stdout);
            output_pos=0;
        }
    }
}
using FastIO::read_int;
using FastIO::write_int;
const int N=1e6+1;
struct Segment_Tree
{
	int sum,ls,rs;
}tree[N*40];
int root[N],cnt,lst[N];
il void update(rg int &id,rg int l,rg int r,rg int p,rg int sum)
{
	tree[++cnt]=tree[id];
	tree[cnt].sum+=sum;
	id=cnt;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)update(tree[id].ls,l,mid,p,sum);
	else update(tree[id].rs,mid+1,r,p,sum);
}
il int query(rg int id,rg int l,rg int r,rg int p)
{
	if(r<p)return 0;
	if(l>=p)return tree[id].sum;
	int mid=l+r>>1,res=0;
	if(p<=mid)res=query(tree[id].ls,l,mid,p);
	res+=query(tree[id].rs,mid+1,r,p);
	return res;
}
signed main()
{
	rg int n=read_int(),Q;
	for(rg int i=1,x;i<=n;i++)
	{
		x=read_int();
		root[i]=root[i-1];
		if(lst[x])update(root[i],1,n,lst[x],-1);
		update(root[i],1,n,i,1);
		lst[x]=i;
	}
	Q=read_int();
	while(Q--)
	{
		rg int l=read_int(),r=read_int();
		write_int(query(root[r],1,n,l));
	}
    FastIO::flush();
	return 0;
}