#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;const int MAXN = 30010;const int M = MAXN * 100;int n,q,tot;int a[MAXN];int T[M],lson[M],rson[M],c[M];int build(int l,int r){    int root = tot++;//    printf ("%d---%d,%d\n",l,r,root);    c[root] = 0;    if(l != r)    {        int mid = (l+r)>>1;        lson[root] = build(l,mid);        rson[root] = build(mid+1,r);    }    return root;}int update(int root,int pos,int val){    int newroot = tot++;//全新的节点    int tmp = newroot;//记录，说明这个点开始是新的树，即将开始找    c[newroot] = c[root] + val;//这个点的值是上一个节点再加上这个新的值（因为这个值保证全新）    int l = 1, r = n;//总区间    while(l < r)//说明还没到最深    {        int mid = (l+r)>>1;//左右分界        if(pos <= mid)//在区间左边，说明右边不用动，直接拿来用，指一下        {            lson[newroot] = tot++;//左边新开节点记录            rson[newroot] = rson[root];//右边承接上一个            newroot = lson[newroot];//去新的点            root = lson[root];//上一个根跟着深入左边            r = mid;//右边不用管了(确定层数)        }        else//左边是还没有更新的节点，但是仍然要指，不然会漏，主要用于删除        {            rson[newroot] = tot++;            lson[newroot] = lson[root];            newroot = rson[newroot];            root = rson[root];            l = mid+1;        }        c[newroot] = c[root] + val;//新的点都要加(因为深入的地方总是带着这个新点)    }    return tmp;//返回节点}int query(int root,int pos){    int ret = 0;    int l = 1, r = n;    while(pos < r)    {        int mid = (l+r)>>1;        if(pos <= mid)//在左边，说明这个点不足，只有深入        {            r = mid;//右边舍去            root = lson[root];//根去左边        }        else        {            ret += c[lson[root]];//在右边，说明左边的这个子区间可以全加上            root = rson[root];            l = mid+1;        }    }    return ret + c[root];//最后一个左区间}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%d",&n) == 1)    {        tot = 0;        for(int i = 1; i <= n; i++)            scanf("%d",&a[i]);        T[n+1] = build(1,n);        map<int,int>mp;        for(int i = n; i>= 1; i--) //T[i]中是对每一个数(位置)的根        {            if(mp.find(a[i]) == mp.end())            {                T[i] = update(T[i+1],i,1);//                printf ("1---%d---%d\n",a[i],T[i+1]);            }            else            {                int tmp = update(T[i+1],mp[a[i]],-1);//为了清除之前的状态，但是不得记录，就当是瞎了                T[i] = update(tmp,i,1);            }            mp[a[i]] = i;        }        scanf("%d",&q);        while(q--)        {            int l,r;            scanf("%d%d",&l,&r);            printf("%d\n",query(T[l],r));//在l这棵树中找r        }    }    return 0;}