#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 100;
const int block = 560;
pair<pair<int,int>,int> query[maxN]; // l,r,and query index;
int input[maxN],res[maxN],freq[maxN];

int ans = 0;

void add (int pos) {
	++freq[input[pos]];
	if (freq[input[pos]] == 1) ++ans;
}

void remove (int pos) {
	--freq[input[pos]];
	if (freq[input[pos]] == 0) --ans;
}

int main () {
	 ios::sync_with_stdio(false);
	 cin.tie(nullptr);
	 cout.tie(nullptr);
	 int T = 1;
	 //~ cin >> T;
	 for (int test_case = 1; test_case <= T; ++test_case) {
		 int n,q;
		 cin >> n;
		 for (int i = 0; i < n; ++i) cin >> input[i];
		 cin >> q;
		 for (int i = 0; i < q; ++i) {
			 cin >> query[i].first.first >> query[i].first.second;
			 query[i].second = i;
			 --query[i].first.first,--query[i].first.second;
		 }
		 sort (query,query + q,[&](pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
			 if (a.first.first / block != b.first.first / block) {
				 return a.first.first / block < b.first.first / block;
			 } 
			 return a.first.second < b.first.second;
		 });
		 int l = 0,r = -1;
		 for (int i = 0; i < q; ++i) {
			 while (l > query[i].first.first) --l,add(l);
			 while (r < query[i].first.second) ++r,add(r);
			 while (l < query[i].first.first) remove(l),++l;
			 while (r > query[i].first.second) remove(r),--r;
			 res[query[i].second] = ans;
		 }
		 for (int i = 0; i < q; ++i) cout << res[i] << '\n';
	 }
	 //~ cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}