#include <bits/stdc++.h>
using namespace std;
int inf =1e9+7;
vector<vector<int> > mt(2000001,vector<int>());

void mergeNodes(vector<int>& res, vector<int>&l, vector<int>& r)
{
    /*
    cout<<"mergeNode\n";
    cout<<"L: ";
    for(int i=0;i<l.size();i++)
        cout<<l[i]<<" ";
    cout<<"\nR: ";
    for(int i=0;i<r.size();i++)
        cout<<r[i]<<" ";
    cout<<endl;
    */
    int i=0,j=0;
    while(i<l.size() && j<r.size())
    {
        if(l[i]<r[j])
        {
            res.push_back(l[i]);
            i++;
        }
        else
        {
            res.push_back(r[j]);
            j++;
        }
    }
    while(i<l.size())
    {
        res.push_back(l[i]);
        i++;
    }
    while(j<r.size())
    {
        res.push_back(r[j]);
        j++;
    }
    /*
    cout<<"res: ";
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
    cout<<endl;
    */
}
void buildTree(int si, int ss, int se,vector<int>& arr)
{
    //cout<<"In buildTree "<<ss<<","<<se<<endl;
    if(ss==se)
    {
        mt[si].push_back(arr[ss]);
        //cout<<"Returning from buildTree"<<ss<<","<<se<<endl;
        return;
    }
    int mid=ss+(se-ss)/2;
    buildTree(2*si,ss,mid,arr);
    buildTree(2*si+1,mid+1,se,arr);
    mergeNodes(mt[si],mt[2*si],mt[2*si+1]);
    //cout<<"Returning from buildTree"<<ss<<","<<se<<endl;
}
int query(int si, int ss, int se, int qs, int qe, int k)
{
    //cout<<"In query "<<qs<<","<<qe<<endl;
    if(qe<ss || qs>se)
    {
        //cout<<"Completely Outside: \n";
        //cout<<"Returning query "<<qs<<","<<qe<<" with res=0"<<endl;
        return 0;
    }

    if(ss>=qs && se<=qe)
    {
        int res=mt[si].size()-(upper_bound(mt[si].begin(),mt[si].end(),k)-mt[si].begin());
        //cout<<"Completely inside: \n";
        //cout<<"Returning query "<<qs<<","<<qe<<" with res="<<res<<endl;
        return res;
    }
    //cout<<"Overlapping: ";
    int mid = ss + (se-ss)/2;
    int l= query(2*si,ss,mid,qs,qe,k);
    int r= query(2*si+1,mid+1,se,qs,qe,k);
    int res= l+r;
    //cout<<"Returning query "<<qs<<","<<qe<<" with res="<<res<<endl;
    return res;
}
void printTree(int si, int ss, int se)
{
    cout<<ss<<", "<<se<<endl;
    for(int i=0;i<mt[si].size();i++)
        cout<<mt[si][i]<<" ";
    cout<<endl;
    if(ss==se)
        return;
    int mid= ss+(se-ss)/2;
    printTree(2*si,ss,mid);
    printTree(2*si+1,mid+1,se);
}
int main()
{
    //printf("%d",inf);
    int n,q,i,qs,qe;
    scanf("%d %d",&n,&q);
    vector<int> colors(n+1);
    for(i=1;i<=n;i++)
        scanf("%d",&colors[i]);
    vector<int> nextOccurIdx(n+1);
    map<int,int> occurIdx;
    for(i=n;i>0;i--)
    {
        if(occurIdx.find(colors[i])==occurIdx.end())
            nextOccurIdx[i]=inf;
        else
            nextOccurIdx[i]=occurIdx[colors[i]];

        occurIdx[colors[i]]=i;
    }
    /*
    for(i=1;i<=n;i++)
        cout<<nextOccurIdx[i]<<" ";
    cout<<endl;
    */
    buildTree(1,1,n,nextOccurIdx);
    //cout<<"BuidTreeFinished\n";
    //printTree(1,1,n);
    /*
    for(i=0;i<n;i++)
        cout<<mt[1][i]<<" ";
    cout<<endl;
    */
    //cout<<n-(upper_bound(mt[1].begin(),mt[1].end(),n)-mt[1].begin())<<endl;
    while(q--)
    {
        scanf("%d %d",&qs,&qe);
        printf("%d\n",query(1,1,n,qs,qe,qe));
    }
    return 0;
}


Measured memory_bytes: 142872