#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e9
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector < pair<ll, ll> > vii;
typedef long double ld;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
ll n, q, curL, curR, l, r, cnt[1000005], a[300005], ans, ans1[200005];
vector<pair<ii, ll> > query;
bool cmp(pair<ii, ll> a, pair<ii, ll> b){
if(a.fi.fi/int(sqrt(n)) < b.fi.fi/int(sqrt(n))){
return 1;
}
else if(a.fi.fi/int(sqrt(n)) == b.fi.fi/int(sqrt(n))){
return a.fi.se <= b.fi.se;
}
else{
return 0;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
for(int i = 0; i < q; i++){
cin >> l >> r;
query.pb(mp(mp(l,r), i));
}
sort(query.begin(),query.end(),cmp);
for(int i = 0; i < q; i++){
l = query[i].fi.fi;
r = query[i].fi.se;
while(curR < r){
curR++;
cnt[a[curR]]++;
if(cnt[a[curR]]==1){
ans++;
}
}
while(r < curR){
cnt[a[curR]]--;
if(cnt[a[curR]]==0){
ans--;
}
curR--;
}
while(l < curL){
curL--;
cnt[a[curL]]++;
if(cnt[a[curL]]==1){
ans++;
}
}
while(curL < l){
cnt[a[curL]]--;
if(cnt[a[curL]]==0){
ans--;
}
curL++;
}
ans1[query[i].se]=ans;
}
for(int i = 0; i < q; i++){
printf("%lld\n", ans1[i]);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZmJvIGZpbmRfYnlfb3JkZXIKI2RlZmluZSBvb2sgb3JkZXJfb2Zfa2V5CiNkZWZpbmUgSU5GIDFlOQogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8bGwsbGw+IGlpOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmk7CnR5cGVkZWYgdmVjdG9yIDwgcGFpcjxsbCwgbGw+ID4gdmlpOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHNldDxpbnQ+OjppdGVyYXRvciBzaXQ7CnR5cGVkZWYgbWFwPGludCxpbnQ+OjppdGVyYXRvciBtaXQ7CnR5cGVkZWYgdmVjdG9yPGludD46Oml0ZXJhdG9yIHZpdDsKIApsbCBuLCBxLCBjdXJMLCBjdXJSLCBsLCByLCBjbnRbMTAwMDAwNV0sIGFbMzAwMDA1XSwgYW5zLCBhbnMxWzIwMDAwNV07CnZlY3RvcjxwYWlyPGlpLCBsbD4gPiBxdWVyeTsKIApib29sIGNtcChwYWlyPGlpLCBsbD4gYSwgcGFpcjxpaSwgbGw+IGIpewoJaWYoYS5maS5maS9pbnQoc3FydChuKSkgPCBiLmZpLmZpL2ludChzcXJ0KG4pKSl7CgkJcmV0dXJuIDE7Cgl9CgllbHNlIGlmKGEuZmkuZmkvaW50KHNxcnQobikpID09IGIuZmkuZmkvaW50KHNxcnQobikpKXsKCQlyZXR1cm4gYS5maS5zZSA8PSBiLmZpLnNlOwoJfQoJZWxzZXsKCQlyZXR1cm4gMDsKCX0KfQogCmludCBtYWluKCl7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpOwogICAgY2luID4+IG47CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKyl7CgkJY2luID4+IGFbaV07Cgl9CgljaW4gPj4gcTsKCWZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspewoJCWNpbiA+PiBsID4+IHI7CgkJcXVlcnkucGIobXAobXAobCxyKSwgaSkpOwoJfQoJc29ydChxdWVyeS5iZWdpbigpLHF1ZXJ5LmVuZCgpLGNtcCk7Cglmb3IoaW50IGkgPSAwOyBpIDwgcTsgaSsrKXsKCQlsID0gcXVlcnlbaV0uZmkuZmk7CgkJciA9IHF1ZXJ5W2ldLmZpLnNlOwoJCXdoaWxlKGN1clIgPCByKXsKCQkJY3VyUisrOwoJCQljbnRbYVtjdXJSXV0rKzsKCQkJaWYoY250W2FbY3VyUl1dPT0xKXsKCQkJCWFucysrOwoJCQl9CgkJfQoJCXdoaWxlKHIgPCBjdXJSKXsKCQkJY250W2FbY3VyUl1dLS07CgkJCWlmKGNudFthW2N1clJdXT09MCl7CgkJCQlhbnMtLTsKCQkJfQoJCQljdXJSLS07CgkJfQoJCXdoaWxlKGwgPCBjdXJMKXsKCQkJY3VyTC0tOwoJCQljbnRbYVtjdXJMXV0rKzsKCQkJaWYoY250W2FbY3VyTF1dPT0xKXsKCQkJCWFucysrOwoJCQl9CgkJfQoJCXdoaWxlKGN1ckwgPCBsKXsKCQkJY250W2FbY3VyTF1dLS07CgkJCWlmKGNudFthW2N1ckxdXT09MCl7CgkJCQlhbnMtLTsKCQkJfQoJCQljdXJMKys7CgkJfQoJCWFuczFbcXVlcnlbaV0uc2VdPWFuczsKCX0KCWZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspewoJCXByaW50ZigiJWxsZFxuIiwgYW5zMVtpXSk7Cgl9CgkKfQo=