#include <bits/stdc++.h>
//#include "incursion.h"
using namespace std;
#define ll long long
const int N=5e5+1;
int dp[N];
int a[N];
int c;
int answ;
struct three{
int fi,se,th;
};
bool chack(three a,three b){
if(a.se/c==b.se/c){
return a.th<b.th;
}
return a.se/c<b.se/c;
}
void add(int v){
dp[a[v]]++;
if(dp[a[v]]==3){
answ--;
}
if(dp[a[v]]==2){
answ++;
}
}
void del(int v){
dp[a[v]]--;
if(dp[a[v]]==2){
answ++;
}
if(dp[a[v]]==1){
answ--;
}
}
void upsolve(){
int n,q;
cin>>n>>q;
c=sqrt(n);
unordered_map<int,int> mp;
int u=0;
for(int i=1;i<=n;++i){
cin>>a[i];
if(mp.find(a[i])==mp.end()){
u++;
mp.insert({a[i],u});
}
a[i]=mp[a[i]];
}
vector<three> mas;
for(int i=0;i<q;++i){
int x,y,z;
cin>>x>>y;
mas.push_back({i,x,y});
}
sort(mas.begin(),mas.end(),chack);
int l=1;
int r=1;
add(1);
vector<int> o(q);
for(int i=0;i<q;++i){
while(l>mas[i].se){
l--;
add(l);
}
while(r<mas[i].th){
r++;
add(r);
}
while(l<mas[i].se){
del(l);
l++;
}
while(r>mas[i].th){
del(r);
r--;
}
o[mas[i].fi]=answ;
}
for(int i=0;i<q;++i){
cout<<o[i]<<'\n';
}
}
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int t;
t=1;
while(t--){
upsolve();
}
return 0;
}
