/*
problem :
created : Programmer_juruo
*/

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

#define N 10000005
#define lowbit(x) x & (-x)
#define Rep(i, n) for(int i = 1; i <= n; i++)
#define rep(i, a, n) for(int i = a; i <= n; i++)
#define Rep2(i, n) for(int i = 0; i < n; i++)
#define dbg(x) cout << #x ":" << x << endl;
#define Se second
#define Fi first
#define Mp make_pair
#define Pb push_back
#define int long long
typedef pair<int, int> Pii;
typedef priority_queue<int> Pq;
typedef long long ll;

int n, m;

inline int Read() {
	int y = 0, f = 1;char c = getchar();
	while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}
	while(isdigit(c)) {y = y*10 + (c - '0'), c = getchar();}
	return y*f;
}
inline void read(int &x){x = Read();}
int tr[N];

void add(int p, int val){for(int i = p;i <= n * 2;i += lowbit(i))tr[i] += val;return;}
int Query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += tr[i];return res;}

int a[N]; 	
struct Node {
	int l, r, x;
}T[N];
int ans[N];
bool cmp(Node x, Node y) {
	return x.r < y.r;
}
map<int,int> Map; 
void work() {
	n = Read();
	Rep(i, n) {
		cin >> a[i];
	}
	m = Read();
//	cout << "*";
	Rep(i, m) {
		T[i].l = Read(), T[i].r = Read();
		T[i].x = i;
	}
//	cout << "(=*";
	sort(T+1, T+1+n, cmp);
	int nxt = 1;
	Rep(i, n){
		rep(j, nxt, T[i].r) {
			if(Map[a[j]]) {
				add(Map[a[j]], -1);
			}
			Map[a[j]] = j;
			add(j, 1);
		}
		ans[T[i].x] = Query(T[i].r) - Query(T[i].l-1);
		nxt = T[i].r+1;
	}
	Rep(j, m) {
		printf("%d\n", ans[j]);
	}
}

signed main() {
  //freopen("1.in", "r", stdin);
  //freopen("1.out", "w", stdout);
  int T = 1;

  //cin >> T;

  while(T--) {
  	work();
  }

  return 0;
}
*/