#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,vector<ll>> mp;
vector<ll> a;
ll k,cnt=0;
bool check(vector<ll> f,vector<ll> g){
if(f[0]/k==g[0]/k) return f[1]<g[1];
return f[0]<g[0];
}
void rem(ll x){
if(a[x]==3) cnt++;
if(a[x]==2) cnt--;
a[x]--;
}
void add(ll x){
if(a[x]==1) cnt++;
if(a[x]==2) cnt--;
a[x]++;
}
int main(){
ll n,q,i,j,l=0,r=0;
cin>>n>>q;
a.resize(n+1);
vector<ll> ans(q);
k=sqrt(n);
for(i=1 ; i<=n ; i++){
cin>>a[i];
mp[a[i]].push_back(i);
}
i=0;
for(auto v:mp){
for(j=0 ; j<v.second.size() ; j++){
a[v.second[j]]=i;
}
i++;
}
vector<vector<ll>> x(q,vector<ll>(3));
for(i=0 ; i<q ; i++){
cin>>x[i][0]>>x[i][1];
x[i][2]=i;
}
sort(x.begin(),x.end(),check);
for(i=x[0][0] ; i<=x[0][1] ; i++){
add(a[i]);
}
ans[x[0][2]]=cnt;
l=x[0][0];
r=x[0][1];
for(i=1 ; i<q ; i++){
while(l<x[i][0]){
rem(a[l]);
l++;
}
while(r<x[i][1]){
r++;
add(a[r]);
}
while(r>x[i][1]){
rem(a[r]);
r--;
}
while(l>x[i][0]) {
l--;
add(a[l]);
}
ans[x[i][2]]=cnt;
}
for(i=0 ; i<q ; i++){
cout<<ans[i]<<"\n";
}
return 0;
}
