#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define ll long long
using namespace std;
struct query
{
/*L denotes the left bound of query*/
/*R denotes the right bound of the query*/
/*i denotes the index */
int L, R, i;
};
int freq[1000005]; /* array for storing the frequency of elements*/
int A[30005]; /*Given array*/
int BLK; /*size of bloks*/
int cnt; /*stores the number of distinct elements in the range [currL: currR]
/*function for adding xth element into existing segment*/
void add(int x)
{
freq[ A[x] ]++;
if(freq[ A[x] ] == 1)
cnt++;
}
/*function for removing xth element from existing range*/
void remove(int x)
{
freq[ A[x] ]--;
if(freq[ A[x] ] == 0)
cnt--;
}
/*a comparator function to sort the queries*/
bool comp(query q1,query q2)
{
int BLK1 = q1.L/BLK;
int BLK2 = q2.L/BLK;
if(BLK1 != BLK2) /* if they lie in the same block*/
return q1.L < q2.L;
return q1.R < q2.R;
}
void I_m_Beast()
{
int n,q,l,r;
cin >> n;
for(int i = 0; i < n; i++)
cin >> A[i];
BLK = sqrt(n);
cin >> q;
vector< query > v; /*for storing the queries*/
query q1;
for(int i = 0; i < q; i++)
{
cin >> l >> r;
l--;
r--;
q1.L = l;
q1.R = r;
q1.i = i;
v.pb(q1);
}
sort(v.begin(), v.end(), comp);
int currL = 0,currR = -1;
memset(freq, 0, sizeof(freq));
int ans[q];/*array for storing answer of queries*/
int L,R;
for(int i = 0; i < v.size(); i++)
{
q1 = v[i];
L = q1.L;
R = q1.R;
while(currR < R)
{
currR++;
add(currR);
}
while(currR > R)
{
remove(currR);
currR--;
}
while(currL < L)
{
remove(currL);
currL++;
}
while(currL > L)
{
currL--;
add(currL);
}
ans[q1.i] = cnt;
}
for(int i = 0; i < q; i++)
cout << ans[i] << endl;
}
int main()
{
fastio;
int t;
// cin>>t;
t = 1;
while(t--)
{
I_m_Beast();
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBmYXN0aW8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7IGNvdXQudGllKE5VTEwpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbGwgbG9uZyBsb25nIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IHF1ZXJ5CnsKCS8qTCBkZW5vdGVzIHRoZSBsZWZ0IGJvdW5kIG9mIHF1ZXJ5Ki8KCS8qUiBkZW5vdGVzIHRoZSByaWdodCBib3VuZCBvZiB0aGUgcXVlcnkqLwoJLyppIGRlbm90ZXMgdGhlIGluZGV4ICovCglpbnQgTCwgUiwgaTsKCQp9OwppbnQgZnJlcVsxMDAwMDA1XTsgLyogYXJyYXkgZm9yIHN0b3JpbmcgdGhlIGZyZXF1ZW5jeSBvZiBlbGVtZW50cyovIAoKaW50IEFbMzAwMDVdOyAvKkdpdmVuIGFycmF5Ki8KaW50IEJMSzsgLypzaXplIG9mIGJsb2tzKi8KaW50IGNudDsgLypzdG9yZXMgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBlbGVtZW50cyBpbiB0aGUgcmFuZ2UgW2N1cnJMOiBjdXJyUl0KCi8qZnVuY3Rpb24gZm9yIGFkZGluZyB4dGggZWxlbWVudCBpbnRvIGV4aXN0aW5nIHNlZ21lbnQqLwp2b2lkIGFkZChpbnQgeCkKewoJZnJlcVsgQVt4XSBdKys7CglpZihmcmVxWyBBW3hdIF0gPT0gMSkKCWNudCsrOwp9CgovKmZ1bmN0aW9uIGZvciByZW1vdmluZyB4dGggZWxlbWVudCBmcm9tIGV4aXN0aW5nIHJhbmdlKi8gCnZvaWQgcmVtb3ZlKGludCB4KQp7CglmcmVxWyBBW3hdIF0tLTsKCWlmKGZyZXFbIEFbeF0gXSA9PSAwKQoJY250LS07Cn0KCi8qYSBjb21wYXJhdG9yIGZ1bmN0aW9uIHRvIHNvcnQgdGhlIHF1ZXJpZXMqLwpib29sIGNvbXAocXVlcnkgcTEscXVlcnkgcTIpCnsKCWludCBCTEsxID0gcTEuTC9CTEs7CglpbnQgQkxLMiA9IHEyLkwvQkxLOwoJCglpZihCTEsxICE9IEJMSzIpIC8qIGlmIHRoZXkgbGllIGluIHRoZSBzYW1lIGJsb2NrKi8KCXJldHVybiBxMS5MIDwgcTIuTDsKCXJldHVybiBxMS5SIDwgcTIuUjsgCn0Kdm9pZCBJX21fQmVhc3QoKQp7CglpbnQgbixxLGwscjsKCWNpbiA+PiBuOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQljaW4gPj4gQVtpXTsKCUJMSyA9IHNxcnQobik7CgkKCWNpbiA+PiBxOwoJdmVjdG9yPCBxdWVyeSA+IHY7IC8qZm9yIHN0b3JpbmcgdGhlIHF1ZXJpZXMqLwoJcXVlcnkgcTE7Cglmb3IoaW50IGkgPSAwOyBpIDwgcTsgaSsrKQoJewoJCWNpbiA+PiBsID4+IHI7CgkJbC0tOwoJCXItLTsKCQkKCQlxMS5MID0gbDsKCQlxMS5SID0gcjsKCQlxMS5pID0gaTsKCQl2LnBiKHExKTsKCX0KCXNvcnQodi5iZWdpbigpLCB2LmVuZCgpLCBjb21wKTsKCWludCBjdXJyTCA9IDAsY3VyclIgPSAtMTsKCW1lbXNldChmcmVxLCAwLCBzaXplb2YoZnJlcSkpOwoJaW50IGFuc1txXTsvKmFycmF5IGZvciBzdG9yaW5nIGFuc3dlciBvZiBxdWVyaWVzKi8KCWludCBMLFI7Cglmb3IoaW50IGkgPSAwOyBpIDwgdi5zaXplKCk7IGkrKykKCXsKCQlxMSA9IHZbaV07CgkJTCA9IHExLkw7CgkJUiA9IHExLlI7CgkJd2hpbGUoY3VyclIgPCBSKQoJCXsKCQkJY3VyclIrKzsKCQkJYWRkKGN1cnJSKTsgCQoJCX0KCQl3aGlsZShjdXJyUiA+IFIpCgkJewoJCQlyZW1vdmUoY3VyclIpOyAJCgkJCWN1cnJSLS07CgkJfQoJCXdoaWxlKGN1cnJMIDwgTCkKCQl7CgkJCXJlbW92ZShjdXJyTCk7CgkJCWN1cnJMKys7CgkJfQoJCXdoaWxlKGN1cnJMID4gTCkKCQl7CgkJCWN1cnJMLS07CgkJCWFkZChjdXJyTCk7CgkJfQoJCWFuc1txMS5pXSA9IGNudDsKCX0KCWZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspCgkgY291dCA8PCBhbnNbaV0gPDwgZW5kbDsKfQppbnQgbWFpbigpCnsKCWZhc3RpbzsKCWludCB0OwovLwljaW4+PnQ7Cgl0ID0gMTsKCXdoaWxlKHQtLSkKCXsKCQlJX21fQmVhc3QoKTsKCX0KCXJldHVybiAwOwp9