#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1000005;
long long c[N] , a[N],booll[N] , nnn[N];
int n , q , ww;
map<int, int> mp;
struct Node{
	int  l , r , pos;
}query[N];
bool cmp(Node a , Node b){
	return a.r < b.r;
}
void add(int x , int d){
	for(int i = x ; i <= n ; i += i & -i) c[i] += d;
}
long long sum(int x){
	long long ret = 0;
	for(int i = x ; i ; i -= i & -i) ret += c[i];
	return ret;
}
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	cin >> q;
	for(int i = 1 ; i <= q ; i++){
		cin >> query[i].l >> query[i].r;
		query[i].pos = i;
	}
	sort(query +1 , query + n + 1 , cmp);
	int num = 1;
	for(int i = 1 ; i <= q ; i++){
		for(int j = num ; j <= query[i].r ; j++){
			if(booll[a[j]]){
				add(booll[a[j]] ,- 1);
			}
			add(j,1);
			booll[a[j]] = j;
		}
		num = query[i].r +1;
		nnn[query[i].pos] = sum(query[i].r) - sum(query[i].l - 1);
	}
	for(int i = 1 ; i <= q  ; i++){
		cout << nnn[i] << endl;
	}
}