大概思路是求出原数组的每一个元素 a[i] 其之前出现得最晚的相同元素的下标 pos[i] ，询问时就看右端点 i，i 属于 [l, r]，与区间内 pos[i] 的大小关系

#include <bits/stdc++.h>
#define rep(c, a, b) for (int c = a; c <= b; c ++)
#define per(c, a, b) for (int c = a; c >= b; c --) 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9')
	{if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0'&&ch <= '9')
	{x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}
void write(int x){
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0'); return; 
}
using namespace std;
const int N = 1e6 + 10;
int a[N], vis[N], pos[N];
int bl[N], ans[N], L[N], R[N];
void cre(int n){
	int k = 0.5 * sqrt(n) + 1;
	rep(i, 1, bl[n]){
		L[i] = (i - 1) * k + 1;
		R[i] = L[i] + k - 1;
		R[i] = min(R[i], n);
		ans[i] = k;
		rep(j, L[i], R[i])
			if (pos[j] >= L[i]) ans[i] --;
	}
}
int ask(int l, int r){
	if (bl[l] != bl[r]){
//		cout << "Case1: " << endl;
		int ret = 0;
		rep(i, l, R[bl[l]]) if (pos[i] < l) ret ++;
//		cout << "[" << l << ", " << R[bl[l]] << "]---" << "Step1's ret: " << ret << endl;
		rep(i, bl[l] + 1, bl[r] - 1) ret += ans[i];
//		cout << "[" << L[bl[l]] + 1 << ", " << R[bl[r] - 1] << "]---" << "Step2's ret: " << ret << endl;
		per(i, r, L[bl[r]]) if (pos[i] < l) ret ++;
//		cout << "[" << L[bl[r]] << ", " << r << "]---" << "Step3's ret: " << ret << endl;
		return ret;
	}
	else{
//		cout << "Case2: " << endl;
		int ret = 0;
		rep(i, l, r) if (pos[i] < l) ret ++;
//		cout << "Ret: " << ret << endl;
		return ret;
	}
}
int main(){
	int n = read();
	int k = 0.5 * sqrt(n) + 1;
	rep(i, 1, n){
		a[i] = read();
		pos[i] = vis[a[i]];
		vis[a[i]] = i;
		bl[i] = (i - 1) / k + 1;
	} 
	int m = read(); cre(n);
//	cout << "belongs: " << endl;
//	rep(i, 1, n){
//		cout << bl[i] << " ";
//	}cout << endl;
//	cout << "positions: " << endl;
//	rep(i, 1, n){
//		cout << pos[i] << " ";
//	}cout << endl;
//	cout << "L[x] && R[x]: " << endl;
//	rep(i, 1, bl[n]){
//		cout << L[i] << " " << R[i] << endl;
//	}
//	cout << "ans[x]: " << endl;
//	rep(i, 1, bl[n]){
//		cout << ans[i] << " ";
//	}cout << endl;
//	cout << "-------------" << endl;
	rep(i, 1, m){
		int l = read(), r = read();
		int sum = ask(l, r);
		printf("%d\n", sum);
	}
	return 0;
}