#include <bits/stdc++.h> 
using namespace std;  
 
typedef long long ll;  
typedef pair<int, int> ii;  
 
const int INF = 1e9;  
const ll LINF = 1e18;  
const int N = 3e4 + 5; 
const int Q = 2e5 + 5; 
const int MAX_A = 1e6 + 5; 
 
struct query {
	int l, i;  
};
 
int n, q; 
int a[N]; 
vector<query> queries[N]; // queries[R]: danh sách những truy vấn có đầu mút r == R 
int last[MAX_A]; // last[x] = i gần nhất sao cho a[i] == x
int pre[N]; // pre[i] = j gần nhất sao cho a[j] == a[i] 
int ans[Q];
 
int ft[N]; 
 
void update(int i, int val) {
	for (; i <= n; i += i & (-i)) ft[i] += val; 
}
 
int getSum(int i) {
	int ans = 0;   
	for (; i > 0; i -= i & (-i)) ans += ft[i]; 
	return ans; 
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);  	
	cin >> n; 
	for (int i = 1; i <= n; i++) cin >> a[i]; 
 
	cin >> q; 
	for (int i = 1; i <= q; i++) {
		int l, r; 
		cin >> l >> r;  
		queries[r].push_back({l, i}); 
	}
 
	for (int i = 1; i <= n; i++) {
		pre[i] = last[a[i]]; 
		last[a[i]] = i;  
	}
 
	for (int r = 1; r <= n; r++) {
		// xoá chỉ số ở đằng trước mà đại diện cho a[r]
		if (pre[r] > 0) update(pre[r], -1); 
		// cho r làm chỉ số đại diện cho a[r]
		update(r, 1); 
		// trả lời truy vấn
		for (auto& q : queries[r]) {
			ans[q.i] = getSum(r) - getSum(q.l - 1); 
		}
	}
 
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; 
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IAp1c2luZyBuYW1lc3BhY2Ugc3RkOyAgCgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsgIAp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IGlpOyAgCgpjb25zdCBpbnQgSU5GID0gMWU5OyAgCmNvbnN0IGxsIExJTkYgPSAxZTE4OyAgCmNvbnN0IGludCBOID0gM2U0ICsgNTsgCmNvbnN0IGludCBRID0gMmU1ICsgNTsgCmNvbnN0IGludCBNQVhfQSA9IDFlNiArIDU7IAoKc3RydWN0IHF1ZXJ5IHsKCWludCBsLCBpOyAgCn07CgppbnQgbiwgcTsgCmludCBhW05dOyAKdmVjdG9yPHF1ZXJ5PiBxdWVyaWVzW05dOyAvLyBxdWVyaWVzW1JdOiBkYW5oIHPDoWNoIG5o4buvbmcgdHJ1eSB24bqlbiBjw7MgxJHhuqd1IG3DunQgciA9PSBSIAppbnQgbGFzdFtNQVhfQV07IC8vIGxhc3RbeF0gPSBpIGfhuqduIG5o4bqldCBzYW8gY2hvIGFbaV0gPT0geAppbnQgcHJlW05dOyAvLyBwcmVbaV0gPSBqIGfhuqduIG5o4bqldCBzYW8gY2hvIGFbal0gPT0gYVtpXSAKaW50IGFuc1tRXTsKCmludCBmdFtOXTsgCgp2b2lkIHVwZGF0ZShpbnQgaSwgaW50IHZhbCkgewoJZm9yICg7IGkgPD0gbjsgaSArPSBpICYgKC1pKSkgZnRbaV0gKz0gdmFsOyAKfQoKaW50IGdldFN1bShpbnQgaSkgewoJaW50IGFucyA9IDA7ICAgCglmb3IgKDsgaSA+IDA7IGkgLT0gaSAmICgtaSkpIGFucyArPSBmdFtpXTsgCglyZXR1cm4gYW5zOyAKfQogCmludCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7ICAJCgljaW4gPj4gbjsgCglmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIGNpbiA+PiBhW2ldOyAKCQoJY2luID4+IHE7IAoJZm9yIChpbnQgaSA9IDE7IGkgPD0gcTsgaSsrKSB7CgkJaW50IGwsIHI7IAoJCWNpbiA+PiBsID4+IHI7ICAKCQlxdWVyaWVzW3JdLnB1c2hfYmFjayh7bCwgaX0pOyAKCX0KCglmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKCQlwcmVbaV0gPSBsYXN0W2FbaV1dOyAKCQlsYXN0W2FbaV1dID0gaTsgIAoJfQoKCWZvciAoaW50IHIgPSAxOyByIDw9IG47IHIrKykgewoJCS8vIHhvw6EgY2jhu4kgc+G7kSDhu58gxJHhurFuZyB0csaw4bubYyBtw6AgxJHhuqFpIGRp4buHbiBjaG8gYVtyXQoJCWlmIChwcmVbcl0gPiAwKSB1cGRhdGUocHJlW3JdLCAtMSk7IAoJCS8vIGNobyByIGzDoG0gY2jhu4kgc+G7kSDEkeG6oWkgZGnhu4duIGNobyBhW3JdCgkJdXBkYXRlKHIsIDEpOyAKCQkvLyB0cuG6oyBs4budaSB0cnV5IHbhuqVuCgkJZm9yIChhdXRvJiBxIDogcXVlcmllc1tyXSkgewoJCQlhbnNbcS5pXSA9IGdldFN1bShyKSAtIGdldFN1bShxLmwgLSAxKTsgCgkJfQoJfQoKCWZvciAoaW50IGkgPSAxOyBpIDw9IHE7IGkrKykgY291dCA8PCBhbnNbaV0gPDwgJ1xuJzsgCn0K

NQoxIDEgMiAxIDMKMwoxIDUKMiA0CjMgNQo=

5
1 1 2 1 3
3
1 5
2 4
3 5