题意：查询某一段区间中有多少不同的数字。

思路：可以想到把每个数字第一次出现的位置标记为1，不是的则为0，然后前缀和。但是这里是区间查询，有些数在整个数列里不一定是第一个，但是在区间里可能就是第一个了，所以这里要离线处理。

第一次做离线的题，先说一下什么是离线吧。离线就是要知道所有输入以后再处理，最后一次性输出全部。

这里把输入的区间按左端点排序，然后一个一个处理询问，这样相当于在模拟一个类似滑动窗口的东西，当滑动窗口滑到某个区间后，把在上一个区间但不在这个区间的数字取nxt[]（nxt[i]表示的是下一个与a[i]相同的数字（预处理）），即这种颜色不再计算时（单点修改该数字为0），我们再添加在区间中的下一个和它颜色相同的元素（单点修改该数字为1），然后查询前缀和即可。

代码：

int n;
int a[50010];
int d[50010];
int nxt[50010];//下一个与它相同的数
int now[1000010];//上一个值为i的数的位置
bool vis[1000010];//判断之前是否出现过
int ans[200010];
struct qur
{
    int l,r;
    int ans,id;
}q[200010];
bool cmp(qur x,qur y)
{
    return x.l<y.l;
}
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//查询前缀和
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//单点修改
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(!vis[a[i]])add(i,1);
        vis[a[i]]=true;
        if(now[a[i]]!=-1)nxt[now[a[i]]]=i;
        now[a[i]]=i;
    }
    /*for(int i=1;i<=n;i++)
        printf("%d ",nxt[i]);
    printf("\n");*/
}
int main()
{
    int m;
    scanf("%d",&n);
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(nxt,-1,sizeof(nxt));
    memset(now,-1,sizeof(now));
    init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        q[i].id=i;
        scanf("%d%d",&q[i].l,&q[i].r);
    }
    sort(q+1,q+m+1,cmp);
    q[0].l=1;
    /*for(int i=1;i<=n;i++)
        printf("%d ",query(i)-query(i-1));*/
    for(int i=1;i<=m;i++)
    {
        for(int j=q[i-1].l;j<q[i].l;j++)
        {
            int pos=j;
            while(pos!=-1&&pos<q[i].l)
                pos=nxt[pos];
            if(pos!=-1)add(pos,1);
            add(j,0);
        }
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}