Link

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

inline int read(){
	int f = 1,x = 0;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void print(int x){
	if(x > 9)print(x / 10);
	putchar(x % 10 + '0');
}

int belong[1000010], a[30010], sum[1000010], ans[1000010];

struct node{
	int l, r, id;
}m[200010];

int cmp(node a, node b) {
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

signed main(){
	int n = read(), s = sqrt(n);
	for(int i = 1;i <= n;++i)
		for(int j = (i - 1) * s + 1;j <= i * s;++j)
			belong[j] = i;
	for(int i = 1;i <= n;i++){
		a[i] = read();
	}
	int q = read();
	for(int i = 1;i <= q;++i)
		m[i].l = read(), m[i].r = read(), m[i].id = i;
	sort(m + 1, m + 1 + q, cmp);
	int l = 1, r = 0, now = 0;
	for(int i = 1;i <= q;++i){
		int ql = m[i].l, qr = m[i].r;
		while(l < ql)now -= !--sum[a[l++]];
		while(l > ql)now += !sum[a[--l]]++;
		while(r < qr)now += !sum[a[++r]]++;
		while(r > qr)now -= !--sum[a[r--]];
		ans[m[i].id] = now;
	}
	for(int i = 1;i <= q;i++)
		print(ans[i]), putchar('\n');
	return 0;
}