1 #include
2 #include <string>
3 #include
4 #include
5 #include
6 #include
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 Node
14 {
15 int l,r,ans,idx;
16 bool operator <(const Node &rhs)const
17 {
18 return r 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_JUDGE
47 freopen("in.txt","r",stdin);
48 #endif
49 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 )
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 )
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 else
74 {
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 )
83 printf("%d\n",ans[i]);
84 }
85 return 0;
86 }