#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define pb push_back
#define F first
#define S second
const ll siz = 350;
bool comp(iii a,iii b){
if((a.F.F / siz) == (b.F.F / siz)){
return a.F.S < b.F.S;
}
return (a.F.F / siz) < (b.F.F / siz);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin>>n;
ll q;
cin>>q;
map<ll,ll>mp;
ll arr[n];
set<ll>ex;
f(i,0,n){
cin>>arr[i];
ex.insert(arr[i]);
}
ll pos = 0;
for(auto x:ex){
mp[x] = pos;
pos++;
}
f(i,0,n){
arr[i] = mp[arr[i]];
}
ll siz[n] = {0};
ll posa[n] = {0};
ll ans[q];
vector<iii>ask;
f(i,0,q){
ll a,b;
cin>>a>>b;
a--;
b--;
ask.pb(iii(ii(a,b),i));
}
sort(ask.begin(),ask.end(),comp);
ll l = 0,r = 0;
siz[0] = (ll)ex.size() - 1;
siz[1]++;
posa[arr[0]]++;
for(auto x:ask){
while(l > x.F.F){
l--;
posa[arr[l]]++;
siz[posa[arr[l]]-1]--;
siz[posa[arr[l]]]++;
}
while(r < x.F.S){
r++;
posa[arr[r]]++;
siz[posa[arr[r]]-1]--;
siz[posa[arr[r]]]++;
}
while(l < x.F.F){
posa[arr[l]]--;
siz[posa[arr[l]]+1]--;
siz[posa[arr[l]]]++;
l++;
}
while(r > x.F.S){
posa[arr[r]]--;
siz[posa[arr[r]]+1]--;
siz[posa[arr[r]]]++;
r--;
}
ans[x.S] = siz[2];
}
f(i,0,q){
cout<<ans[i]<<"\n";
}
}
