#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,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(mp[x]==3) cnt++;
if(mp[x]==2) cnt--;
mp[x]--;
}
void add(ll x){
if(mp[x]==1) cnt++;
if(mp[x]==2) cnt--;
mp[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];
}
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--;
}
ans[x[i][2]]=cnt;
}
for(i=0 ; i<q ; i++){
cout<<ans[i]<<"\n";
}
return 0;
}
