#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000005;
int n,a[maxn],pos[maxn],m;
int rk[maxn],L[maxn],R[maxn];
int c[maxn],Add[maxn],ans[maxn];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	for(;x <= n;x += lowbit(x)) {
		c[x] += y;
	}
	return ;
}
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x)) {
		ans += c[x];
	}
	return ans;
}
bool cmp(int a,int b)  {
	return R[a] == R[b] ? L[a] < L[b] : R[a] < R[b]; 
} 
int read() {
	int s = 0;
	char c = getchar();
	while(c < '0'||c > '9')c = getchar();
	while(c >= '0'&&c <= '9')s = (s << 1) + (s << 3) + (c ^ '0'),c = getchar();
	return s;
} 
int main() {
	freopen("diff.in", "r", stdin);
	freopen("diff.out", "w", stdout);
	n = read();
	for(int i = 1;i <= n;++ i) {
		a[i] = read();
	}
	m = read();
	for(int i = 1;i <= m;++ i) {
		rk[i] = i;
		L[i] = read();
		R[i] = read();
	}
	sort(rk + 1 , rk + 1 + m , cmp);
	int j = 1;
	for(int i = 1;i <= n;++ i) {
		if(Add[a[i]])add(Add[a[i]] , -1);
		add(Add[a[i]] = i , 1);
		while(j <= m&&R[rk[j]] < i)++ j;
		while(j <= m&&R[rk[j]] == i) {
			ans[rk[j]] = query(i) - query(L[rk[j]] - 1);
			++ j;
		}
	}
	for(int i = 1;i <= m;++ i)printf("%d\n",ans[i]);
	return 0;
}