#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<climits>
using namespace std;
const int MAXN = 1e6 + 6;
typedef struct Line{
    int l,r,id;
}Line;
bool cmp(Line x,Line y){
    return x.r < y.r;
}
int c[MAXN],a[MAXN],pre[MAXN],last[MAXN],ans[MAXN];
Line line[MAXN];
int n,m;
int lowbit(int x){
    return x & -x;
}
void add(int pos,int v){
    for(int i = pos; i <= n; i += lowbit(i)){
        c[i] += v;
    }
}
int query(int pos){
    int res = 0;
    for(int i = pos; i; i -= lowbit(i)){
        res += c[i];
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        pre[a[i]] = last[a[i]];
        last[a[i]] = i;
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        int l,r;
        cin >> l >> r;
        line[i].l = l - 1;
        line[i].r = r;
        line[i].id = i;
    }
    sort(line + 1,line + 1 + m,cmp);
    int pos = 1;
    for(int i = 1; i <= m; i++){
        while(pre[a[pos]] <= line[i].l + 1 && pos <= line[i].r){
            add(pos,1);
            if(pre[a[pos]]){
                add(pre[a[pos]],-1);
            }
            pos++;
        }
        ans[line[i].id] = query(line[i].r) - query(line[i].l);
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << endl;
    }
}