RT，但是没写离散化（所以不知道咋T了

#include<iostream>
#include<algorithm>
#include<cmath>
#define gc getchar
using namespace std;
int n,Q,block;
struct node{
	int id,l,r;
}q[1000010];
int a[1000010],ans[1000010],t[1000010],nans;
template<typename T>
inline void read(T& a){a=0;int f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}while(ch>='0'&&ch<='9')a=(a<<1)+(a<<3)+(ch^48),ch=gc();a*=f;}
int cmp(node n1,node n2){
	if(n1.id/block==n2.id/block){
		if((n1.id/block)&1) return n1.r<n2.r;
		else return n1.r>n2.r;
	}
	return n1.id/block<n2.id/block;
}
void add(int x){
	t[a[x]]++;
	if(t[a[x]]==3) nans--;
	if(t[a[x]]==2) nans++;
}
void del(int x){
	t[a[x]]--;
	if(t[a[x]]==1) nans--;
	if(t[a[x]]==2) nans++;
}
int main(){
	read(n),read(Q);
	block=sqrt(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=Q;i++){
		read(q[i].l),read(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+Q+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=Q;i++){
		if(q[i].l==q[i].r){
			ans[q[i].id]=0;
			continue;
		}
		ans[q[i].id]=ans[q[i].id-1];
		while(l>q[i].l) add(--l);
		while(l<q[i].l) del(l++);
		while(r>q[i].r) del(r--);
		while(r<q[i].r) add(++r);
		ans[q[i].id]=nans;
	}
	for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}