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

const int N = 1e6 + 33;

int a[N], pos[N], ans[N], t[N], n, m;
bool book[N];

struct swqj{
	int l, r, num;
}b[N];

bool cmp(swqj e, swqj r){
	if(e.r != r.r)return e.r < r.r;
	else return e.l < r.l;
}

void add(int x, int y){
	for( ; x <= n; x += x & -x){
		t[x] += y;
	}
}

int sum(int x){
	int y = 0;
	for( ; x; x -= x & -x){
		y +=t[x];
	}
	return y;
}

int read(){
	char ch = getchar();
	int s = 0, w = 1;
	while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){s=s*10+ch-'0';ch=getchar();}
	return s * w;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)	a[i] = read();;
	cin >> m;
	for(int i = 1; i <= m; i++){
		b[i].l = read(); b[i].r = read();
		b[i].num = i;
	} 
	sort(b + 1, b + m + 1, cmp);
	int cnt = 1;
	for(int i = 1; i <= n; ){
		while(i <= b[cnt].r){ 
			add(i, 1);
			if(book[a[i]]){
				add(pos[a[i]], -1);
			}
			book[a[i]] = 1;// a[i] 这个数出现了 
			pos[a[i]] = i; // a[i] 这个数最后出现的位置是i  
			i++;
		}
		ans[b[cnt].num] = sum(b[cnt].r) - sum(b[cnt].l - 1);
		while(b[cnt + 1].r == b[cnt].r){
			cnt++;
			ans[b[cnt].num] = sum(b[cnt].r) - sum(b[cnt].l - 1);
		}
		cnt++;
	}
	for(int i = 1; i <= m; i++){
		cout << ans[i] << "\n"; 
	}
	return 0;
}