将权值排序，设权值x排序后在[l,r]出现，x在区间中出现k次，则用[l,l+k-1]为1，[l+k,r]为0来表示x的出现次数
用bitset表示可重集中每个元素的出现次数，用莫队处理出询问区间对应的bitset，通过取and后求1的个数得到答案
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
typedef unsigned int u32;
typedef u32 bits[];
const int N1=,N=N1*;
int _(){
int x=,c=getchar();
while(c<)c=getchar();
while(c>)x=x*+c-,c=getchar();
return x;
}
int n,m,v[N],vs[N];
struct Q{
int l,r,id;
}qs[N];
int pos[N],ps[N];
bool operator<(Q a,Q b){
if(pos[a.l]!=pos[b.l])return pos[a.l]<pos[b.l];
if(a.r!=b.r)return (a.r<b.r)^(pos[a.l]&);
return ;
}
int qp=;
int qt[N],ans[N];
bits now,xs[N1];
void _flip(bits a,int x){a[x>>]^=<<(x&);}
void _clr(bits a){memset(a,,sizeof(int)*(n/+));}
void ins(int x){_flip(now,ps[x]++);}
void del(int x){_flip(now,--ps[x]);}
void _and(bits a,bits b){
int mx=n/+;
for(int i=;i<mx;i+=){
a[]&=b[];
a[]&=b[];
a[]&=b[];
a[]&=b[];
a[]&=b[];
a[]&=b[];
a[]&=b[];
a[]&=b[];
a+=,b+=;
}
}
int c1[];
int _and_c1(bits a,bits b){
int mx=n/+,s1=,s2=,s3=;
for(int i=;i<mx;++i){
u32 x=a[i]&b[i];
s1+=c1[x>>];
s2+=c1[x>>&];
s3+=c1[x&];
}
return s1+s2+s3;
}
void calc(){
int B=n/sqrt(qp)+;
for(int i=;i<n;++i)pos[i]=i/B,ps[v[i]]=v[i];
_clr(now);
for(int i=;i<qp/;++i)qt[i]=;
std::sort(qs,qs+qp);
int L=,R=;
for(int i=;i<qp;++i){
int l=qs[i].l,r=qs[i].r,id=qs[i].id;
while(R<r)ins(v[++R]);
while(L>l)ins(v[--L]);
while(R>r)del(v[R--]);
while(L<l)del(v[L++]);
int t=++qt[id];
if(t==)memcpy(xs[id],now,sizeof(int)*(n/+));
else if(t==)_and(xs[id],now);
else ans[id]-=_and_c1(xs[id],now)*;
}
for(int i=;i<qp/;++i)printf("%d\n",ans[i]);
qp=;
}
int main(){
for(int i=;i<;++i)c1[i]=c1[i>>]+(i&);
n=_(),m=_();
for(int i=;i<n;++i)v[i]=vs[i]=_();
std::sort(vs,vs+n);
for(int i=;i<n;++i)v[i]=std::lower_bound(vs,vs+n,v[i])-vs;
for(int i=;i<m;++i){
ans[qp/]=;
for(int j=;j<;++j){
qs[qp].l=_()-;
qs[qp].r=_()-;
qs[qp].id=qp/;
ans[qs[qp].id]+=qs[qp].r-qs[qp].l+;
++qp;
}
if(qp>=(N1-)*||i+==m)calc();
}
return ;
}