//
//  main.cpp
//  HH的项链
//
//  Created by Qing Liu on 16/3/31.
//  Copyright © 2016年 Qing Liu. All rights reserved.
//

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#define maxn 51000
#define maxm 210000
using namespace std;
typedef pair<pair<int,int>, pair<int, int> > pi;
int fenwick[maxn],basis[maxn],nextc[maxn],p[maxn];
pi que[maxm];
bool comp(const pi &a,const pi &b){
    pair<int, int>tema=a.first;
    pair<int, int>temb=b.first;
    return tema.first!=temb.first?tema.first<temb.first:tema.second<temb.second;
}
int n,mx;
void addx(int p,int r){
    while(p<=n){
        fenwick[p]+=r;
        p+=(p&-p);
    }
    return;
}
map<int,int>mapin;
int sum(int p){
    int ans=0;
    while (p>0) {
        ans+=fenwick[p];
        p-=p&(-p);
    }
    return ans;
}
bool comp1(const pi &a,const pi &b){
    pair<int, int>tema=a.second;
    pair<int, int>temb=b.second;
    return tema.first<temb.first;
}
int main() {
    freopen("diff.in", "r", stdin);
    freopen("diff.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>basis[i];
        mapin[basis[i]]=0;
    }
    map<int,int>::iterator it=mapin.begin();
    int mx=1;
    for (; it!=mapin.end(); it++,mx++) {
        it->second=mx;
    }
    for (int i=1; i<=n; i++) {
        basis[i]=mapin[basis[i]];
    }
    for (int i=n; i>=1; i--) {
        nextc[i]=p[basis[i]];
        p[basis[i]]=i;
    }
    for (int i=1; i<mx; i++) {
        if (p[i]) {
            addx(p[i], 1);
        }
    }
    int m;
    cin>>m;
    for (int i=0; i<m; i++) {
        int l,r;
        cin>>l>>r;
        pair<int, int>temp(l,r);
        pi asd(temp,pair<int, int>(i,0));
        que[i]=asd;
    }
    int l=1;
    sort(que, que+m, comp);
    for (int i=0; i<m; i++) {
        while (que[i].first.first>l) {
            if (nextc[l]) {
                addx(nextc[l], 1);
            }
            l++;
        }
        que[i].second.second=sum(que[i].first.second)-sum(que[i].first.first-1);
    }
    sort(que, que+m, comp1);
    for (int i=0; i<m; i++) {
        cout<<que[i].second.second<<endl;
    }
    return 0;
}