#include<bits/stdc++.h>
#define fou(i,a,b) for (int i = a; i <= b; i++)
#define fod(i,a,b) for (int i = a; i >= b; i--)
#define pb push_back
using namespace std;
const int N = 3*1e6+5;
struct Query {int l, id;};
int n, numQ;
int a[N];
vector<Query> q[N];
map<int,int> trace;
int st[N];
void update(int id, int l, int r, int pos, int val)
{
if (l == r) return void(st[id] = val);
int m = l + (r-l)/2;
if (pos <= m) update(2*id,l,m,pos,val);
else update(2*id+1,m+1,r,pos,val);
st[id] = st[2*id] + st[2*id+1];
}
int get(int id, int l, int r, int s, int e)
{
if (l > e || r < s) return 0;
if (s <= l && r <= e) return st[id];
int m = l + (r-l)/2;
return get(2*id,l,m,s,e) + get(2*id+1,m+1,r,s,e);
}
int ans[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
fou(i,1,n) cin >> a[i];
cin >> numQ;
fou(i,1,numQ)
{
int l,r;
cin >> l >> r;
q[r].pb({l,i});
}
fou(i,1,n)
{
if (trace[a[i]]) update(1,1,n,trace[a[i]],0);
update(1,1,n,i,1);
trace[a[i]] = i;
for (auto r:q[i]) ans[r.id] = get(1,1,n,r.l,i);
}
fou(i,1,numQ) cout << ans[i] << endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBmb3UoaSxhLGIpIGZvciAoaW50IGkgPSBhOyBpIDw9IGI7IGkrKykKI2RlZmluZSBmb2QoaSxhLGIpIGZvciAoaW50IGkgPSBhOyBpID49IGI7IGktLSkKCiNkZWZpbmUgcGIgcHVzaF9iYWNrCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gPSAzKjFlNis1OwoKc3RydWN0IFF1ZXJ5IHtpbnQgbCwgaWQ7fTsKCmludCBuLCBudW1ROwoKaW50IGFbTl07Cgp2ZWN0b3I8UXVlcnk+IHFbTl07CgptYXA8aW50LGludD4gdHJhY2U7CgppbnQgc3RbTl07Cgp2b2lkIHVwZGF0ZShpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IHBvcywgaW50IHZhbCkKewogICAgaWYgKGwgPT0gcikgcmV0dXJuIHZvaWQoc3RbaWRdID0gdmFsKTsKICAgIGludCBtID0gbCArIChyLWwpLzI7CiAgICBpZiAocG9zIDw9IG0pIHVwZGF0ZSgyKmlkLGwsbSxwb3MsdmFsKTsKICAgIGVsc2UgdXBkYXRlKDIqaWQrMSxtKzEscixwb3MsdmFsKTsKICAgIHN0W2lkXSA9IHN0WzIqaWRdICsgc3RbMippZCsxXTsKfQoKaW50IGdldChpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IHMsIGludCBlKQp7CiAgICBpZiAobCA+IGUgfHwgciA8IHMpIHJldHVybiAwOwogICAgaWYgKHMgPD0gbCAmJiByIDw9IGUpIHJldHVybiBzdFtpZF07CiAgICBpbnQgbSA9IGwgKyAoci1sKS8yOwogICAgcmV0dXJuIGdldCgyKmlkLGwsbSxzLGUpICsgZ2V0KDIqaWQrMSxtKzEscixzLGUpOwp9CgppbnQgYW5zW05dOwoKc2lnbmVkIG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7IGNvdXQudGllKE5VTEwpOwogICAgY2luID4+IG47CiAgICBmb3UoaSwxLG4pIGNpbiA+PiBhW2ldOwogICAgY2luID4+IG51bVE7CiAgICBmb3UoaSwxLG51bVEpCiAgICB7CiAgICAgICAgaW50IGwscjsKICAgICAgICBjaW4gPj4gbCA+PiByOwogICAgICAgIHFbcl0ucGIoe2wsaX0pOwogICAgfQogICAgZm91KGksMSxuKQogICAgewogICAgICAgIGlmICh0cmFjZVthW2ldXSkgdXBkYXRlKDEsMSxuLHRyYWNlW2FbaV1dLDApOwogICAgICAgIHVwZGF0ZSgxLDEsbixpLDEpOwogICAgICAgIHRyYWNlW2FbaV1dID0gaTsKICAgICAgICBmb3IgKGF1dG8gcjpxW2ldKSBhbnNbci5pZF0gPSBnZXQoMSwxLG4sci5sLGkpOwogICAgfQogICAgZm91KGksMSxudW1RKSBjb3V0IDw8IGFuc1tpXSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cgp9Cg==