#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
#define cerr if(false)cerr
#define freopen if(false)freopen
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
int n; 
int a[1000010]; int pre[1000010]; int lst[1000010]; int ans[1000010];
struct thing {
    int typ; //0: point -1: query.l(-1) 1: query.r(1)
    int ind; //the index of query
    int x,y; //if point, (x,y). if query, [1,x] [0,y].
    int ntr; //the add time, for debugging.
    bool operator< (thing ant) { if(x != ant.x) return x < ant.x; return (x == 0); }
}b[3000010]; int bcnt;
struct szsz {
    int x[1000010]; int vr;
    int lowbit(int pos) {return pos & -pos;}
    void add(int pos, int k) { cerr<<"add"<<pos<<" "<<k<<endl;
        pos ++; while(pos <= vr) { x[pos] += k; cerr<<"change:"<<pos<<endl;pos += lowbit(pos); } }
    int query(int pos) { cerr<<"query"<<pos<<endl;
        pos ++; int ret = 0; 
        while(pos > 0) { ret += x[pos]; pos -= lowbit(pos); } cerr<<"result:"<<ret<<endl;
        return ret;}
}sz;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    cin >> n; sz.vr = n + 1;
    f(i, 1, n) cin >> a[i];
    f(i, 1, n) { pre[i] = lst[a[i]]; lst[a[i]] = i; }
    f(i, 1, n) { b[++bcnt] = { 0, 0, i, pre[i], i }; } 
    int m; cin >> m;
    f(i, 1, m) { int l, r; cin >> l >> r; 
        b[++bcnt] = { 1, i, r, l - 1, n + i }; b[++bcnt] = { -1, i, l - 1, l - 1, n + i }; }watch(bcnt);
    sort(b + 1, b + bcnt + 1); 
    f(i, 1, bcnt) { cerr<<"thing"<<b[i].typ<<" "<<b[i].ind<<" "<<b[i].x<<" "<<b[i].y<<" "<<b[i].ntr<<endl;
        if(b[i].typ == 0) { sz.add(b[i].y, 1); } 
        else { ans[b[i].ind] += b[i].typ * sz.query(b[i].y); } }
    f(i, 1, m) cout << ans[i] << endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}
/*
2023/1/25
start thinking at h:mm

diagonals: (i, pre_i)
query: [l, r] [0, l - 1]

start coding at 11:02
finish debugging at h:mm
*/