#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;

const int N=5*100005;

struct node{
  int l;
  int r;
  int id;
}u[N];

int z;
bool cool(node a,node b)
{
     if(a.l/z<b.l/z)
        return true;
     if(a.l/z>b.l/z)
        return false;
     return a.r<b.r;
}
int cnt[N];
int cp[N];
int ans[N];
int v[N];

map<int,int>cmp;

int main()
{

     //ios_base:: sync_with_stdio(false); cin.tie(0);
     //freopen("input.in","r",stdin);
        
        int n,q;cin>>n>>q;
        int fuk=0;
        z=sqrt(n);
        
        for(int i=0;i<n;i++)
                scanf("%d",&v[i]),cp[i]=v[i];

        sort(cp,cp+n);
        for(int i=0;i<n;i++)if(cmp.find(cp[i])==cmp.end())cmp[cp[i]]=i+1;
        for(int i=0;i<n;i++)v[i]=cmp[v[i]];
            

                    
        for(int i=0;i<q;i++)
        {
             int l,r;
             scanf("%d %d",&l,&r);
             node tmp;
             tmp.l=l-1;
             tmp.r=r-1;
             tmp.id=i;
             u[i]=tmp;
        }

         sort(u,u+q,cool);

         int st=0,e=0;fuk=0;cnt[v[0]]++;

        for(int i=0;i<q;i++)
        {
            int l=u[i].l;
            int r=u[i].r;
           // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
            
            while(st<l)
            {
                cnt[v[st]]--;
                int gg=cnt[v[st]];
                if(gg==1)
                 {fuk--;}
                else if(gg==2){fuk++;}
                 st++;
            }
            while(st>l)
            {
                 st--;
                 cnt[v[st]]++;
                 int gg=cnt[v[st]];
                 if(gg==2)
                 {
                    fuk++;
                 }
                 else if(gg==3)
                 {
                    fuk--;
                 }
            }
            while(e<r)
            {
                e++;
                cnt[v[e]]++;
                int gg=cnt[v[e]];
                if(gg==2)
                {fuk++;}
               else if(gg==3){fuk--;}
            }
            while(e>r)
            {
               cnt[v[e]]--;
               int gg=cnt[v[e]];
               if(gg==1)
               {fuk--;}
               else if(gg==2){fuk++;}
               e--;
            }            
            ans[u[i].id]=fuk;
        }
        
        for(int i=0;i<q;i++)
            printf("%d\n",ans[i]);

     return 0;
}