1 #include <bits/stdc++.h>

 2

 3 using namespace std;

 4

 5 const int MAXN = 3e4 + 15;

 6 int n, q, a[MAXN], root[MAXN], tot;

 7 struct Node

 8 {

 9     int l, r, c;

10 }T[MAXN*30];

11

12 void build(int &rt, int l, int r)

13 {

14     T[++tot].c = 0;

15     rt = tot;

16     if(l == r)  return;

17     int mid = (l+r)>>1;

18     build(T[rt].l, l, mid);

19     build(T[rt].r, mid + 1, r);

20 }

21 void update(int &cur, int pre,int l, int r, int pos, int val)

22 {

23     T[++tot] = T[pre];

24     cur = tot;

25     T[cur].c += val;

26     if(l == r)  return;

27     int m = (l + r) >> 1;

28     if(pos <= m)

29         update(T[cur].l, T[pre].l, l, m, pos, val);

30     else

31         update(T[cur].r, T[pre].r, m + 1, r, pos, val);

32 }

33 int query(int rt, int l, int r, int pos)

34 {

35

36     if(l >= pos)  return T[rt].c;

37     int ans = 0;

38     int m = (l + r) >>1;

39     if(pos <= m)

40     {

41         ans += T[T[rt].r].c;

42         ans += query(T[rt].l, l, m, pos);

43     }

44     else

45     {

46         ans += query(T[rt].r, m + 1, r, pos);

47     }

48     return ans;

49 }

50 int main()

51 {

52     //freopen("in.txt", "r", stdin);

53     scanf("%d", &n);

54     for(int i = 1; i <= n; i++)

55     {

56         scanf("%d", &a[i]);

57     }

58     tot = 0;

59     build(root[0], 1, n);

60     map<int, int> mp;

61     for(int i = 1; i <= n; i++)

62     {

63         if(mp.find(a[i]) == mp.end())

64             update(root[i], root[i-1], 1, n, i, 1);

65         else

66         {

67             int tmp;

68             update(tmp, root[i-1], 1, n, mp[a[i]], -1);

69             update(root[i], tmp, 1, n, i, 1);

70         }

71         mp[a[i]] = i;

72     }

73     scanf("%d", &q);

74     for(int i = 0; i < q; i++)

75     {

76         int x, y;

77         scanf("%d%d", &x, &y);

78         printf("%d\n", query(root[y], 1, n, x));

79     }

80     return 0;

81 }