#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m,block_size ;
struct query
{
int l,r,idx;
bool operator < (query other) const{
return make_pair((l-1)/block_size,r) < make_pair (( other.l-1)/block_size,other.r);
}
}q[maxn];
int nho[maxn],cnt=0,ans[maxn],a[maxn];
void add (int i)
{
++nho[a[i]];
if (nho[a[i]]==2)
++cnt;
if (nho[a[i]]==3)
--cnt;
}
void remove(int i)
{
--nho[a[i]];
if (nho[a[i]]==2)
++cnt;
if (nho[a[i]]==1)
--cnt;
}
int tmp[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
block_size=sqrt(n);
if (block_size*block_size<n)
block_size++;
int x,y;
for (int i=1;i<=m;i++){
cin>>x>>y;
q[i].l=x;
q[i].r=y;
q[i].idx=i;
}
sort (q+1,q+m+1);
for (int i=1;i<=n;i++)
tmp[i]=a[i];
sort(tmp+1,tmp+n+1);
for (int i=1;i<=n;i++)
a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
int curr_l=1,curr_r=0;
for (int i=1;i<=m;++i){
int L=q[i].l,R=q[i].r,id=q[i].idx;
while (curr_l>L)
add(--curr_l);
while (curr_r<R)
add(++curr_r);
while (curr_l<L)
remove(curr_l++);
while (curr_r>R)
remove(curr_r--);
ans[id]=cnt;
}
for (int i=1;i<=m;i++)
cout<<ans[i]<<'\n';
}
