[+1][doge]莫队是永远卡不掉的

#include<bits/stdc++.h>
using namespace std;
#define belong(x) ((int)ceil((float)x/len))
inline int read(){
	int w = 0, f = 1; char ch = getchar();
	while(ch < '0' or ch > '9') {if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' and ch <= '9') w = w*10 + ch - '0', ch = getchar();
	return w*f;
}
const int maxn = 1e6 + 5;
int N, M, a[maxn], len;
struct node{
	int l, r, id;
	inline bool operator <(const node& x) const{
		return (belong(l)^belong(x.l))?belong(l)<belong(x.l):((belong(l)&1)?r<x.r:r>x.r);
	}
}q[maxn];
int ans[maxn], sum, cnt[maxn];
inline void add(int x){
	if(!cnt[x]) sum ++;
	cnt[x] ++;
}
inline void del(int x){
	if(!(cnt[x]^1)) sum --;
	cnt[x] --;
}
int main(){
	N = read();
	for(int i=1; i<=N; i++) a[i] = read();
	len = 1620; M = read();
	for(int i=1; i<=M; i++){
		int l = read(), r = read();
		q[i] = (node){l, r, i};
	}
	sort(q+1, q+M+1);
	int l = 1, r = 0;
	for(int i=1; i<=M; i++){
		int ql = q[i].l, qr = q[i].r;
		while(l < ql) sum -= !--cnt[a[l++]];
		while(l > ql) sum += !cnt[a[--l]]++;
		while(r < qr) sum += !cnt[a[++r]]++;
		while(r > qr) sum -= !--cnt[a[r--]];
		ans[q[i].id] = sum;
	}
	for(int i=1; i<=M; i++) printf("%d\n", ans[i]);
	return 0;
}