1 #include <cstdio> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8  9 const int maxq = 2e5+10;10 const int maxn = 3e4+10;11 int last[1000050];12 int n,m,c[maxn],ans[200005];13 struct Node14 {15     int l,r,ans,idx;16     bool operator < (const Node &rhs)const17     {18         return r < rhs.r || (r == rhs.r && l < rhs.l);19     }20 }Q[maxq];21 int lowbit(int x)22 {23     return x & -x;24 }25 void add(int x,int d)26 {27     while (x <= maxn)28     {29         c[x] += d;30         x += lowbit(x);31     }32 }33 int sum(int x)34 {35     int ans = 0;36     while (x)37     {38         ans += c[x];39         x -= lowbit(x);40     }41     return ans;42 }43 int a[maxq];44 int main(void)45 {46     #ifndef ONLINE_JUDGE47         freopen("in.txt","r",stdin);48     #endif49     while (~scanf ("%d",&n))50     {51         memset(c,0,sizeof(c));52         memset(last,-1,sizeof(last));53         for (int i = 2; i <= n+1; i++)54             scanf ("%d",a+i);55         scanf ("%d",&m);56         for (int i = 0; i < m; i++)57         {58             Q[i].idx = i;59             scanf ("%d%d",&Q[i].l,&Q[i].r);60             Q[i].l++,Q[i].r++;61         }62         sort(Q,Q+m);63         int pre = 2;64         for (int i = 0; i < m; i++)65         {66             for(int j =  pre; j <= Q[i].r; j++)67             {68                 if (~last[a[j]])69                 {70                     add(last[a[j]],-1);71                     add(j,1);72                 }73                 else74                 {75                     add(j,1);76                 }77                 last[a[j]] = j;78             }79             ans[Q[i].idx] = sum(Q[i].r) - sum(Q[i].l - 1);80             pre = Q[i].r+1;81         }82         for (int i = 0; i < m; i++)83             printf("%d\n",ans[i]);84     }85     return 0;86 }