#include<bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define READ freopen("in.txt","r",stdin)
#define WRITE freopen("out.txt","w",stdout);
#define pb push_back
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define sf(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define sd(x) scanf("%lf",&x);
#define pii pair<int,int>
#define ff first
#define sn second
#define PRINT_CASE  printf("Case %d: ",tc++)
#define PRINT_CASENL  printf("Case %d:\n",tc++)
#define mx 100005
#define lnd tree[ind<<1]
#define rnd tree[(ind<<1)+1]
#define cnd tree[ind]
#define lndp b,(b+e)>>1,(ind<<1)
#define rndp ((b+e)>>1)+1,e,(ind<<1)+1
typedef long long ll;
typedef long long int lln;
ll INF=1<<28;
//typedef long long lld;
const double pi=acos(-1.0);
int fx[]={1,-1,0,0}; //direction array
int fy[]={0,0,1,-1};
int dir[4][2]={1,0,-1,0,0,-1,0,1};

//#define INF 10000
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
struct quer{
    int l,r,in,res;
};

bool cmp(quer a, quer b)
{
    return a.l<b.l;
}
bool cmp2(quer a, quer b)
{
    return a.in<b.in;
}
const int sz=500010;
int tree[4*sz];
int arr[sz],n;
bool vis[sz],sum[sz];
vector<quer>v;
//queue<int>G[sz];
vector<int>G[sz];
void build(int b,int e,int ind)
{
    if(b==e)
    {   if(sum[b])
        tree[ind]=1;
        else
            tree[ind]=0;
        return;
    }
    build(lndp);
    build(rndp);
    cnd=lnd+rnd;
}
int query(int b,int e,int ind,int st,int en)
{
    if(st<=b && e<=en)
    {
        return tree[ind];
    }
    if(st>e || en<b)
        return 0;
    int l=query(lndp,st,en);
    int r=query(rndp,st,en);
   return l+r;
}
void update(int b,int e,int ind,int i,int val)
{
    if(i<=b && i>=e)
    {
        tree[ind]+=val;
        return;
    }
    if(i>e || i<b)
        return;
    update(lndp,i,val);
    update(rndp,i,val);
    cnd=lnd+rnd;
}
int bin(int in,int val)
{
    int l=0,r=G[in].size()-1,mid;
    int ans=-1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(G[in][mid]>=val)
        {
            ans=G[in][mid];
            r=mid-1;
        }
        else
            l=mid+1;

    }
    return ans;
}
int main()
{
//    READ;
    int t,tc=1;
    int q,x,y,mid,l,r,tmp;
   t=1;
    quer p;
    while(t--)
    {
        v.clear();
        mem(vis,0);
        sf2(n,q);
        for(int i=1;i<=n;i++)
        {
            sf(arr[i]);
            if(!vis[arr[i]]){
                sum[i]=true;
            }
            else
                sum[i]=false;
            vis[arr[i]]=true;
            G[arr[i]].pb(i);
        }

        for(int i=0;i<q;i++)
        {
            sf2(l,r);
            p.l=l;
            p.r=r;
            p.in=i;
            p.res=0;
            v.pb(p);

        }
        sort(v.begin(),v.end(),cmp);
        build(1,n,1);
        l=0;
//        cout<<"hhhh"<<endl;
        for(int i=0;i<q;i++)
        {
//            cout<<v[i].l<<" "<<v[i].r<<" "<<v[i].in<<endl;
            for(int  j=l+1;j<v[i].l;j++)
            {
                x=query(1,n,1,j,j);
//                cout<<"j choltese : "<<j<<" "<<x<<endl;;
                if(x==1)
                {
                    update(1,n,1,j,-1);
//                    while(G[arr[j]].front()<v[i].l && !G[arr[j]].empty())
//                    {
//                        G[arr[i]].pop();
//                    }
//                    if(!G[arr[i]].empty())
//                    {
//                        update(1,n,1,G[arr[i]].front(),1);
//
//                    }
                   tmp=bin(arr[j],v[i].l);
                   if(tmp!=-1)
                   {
                       update(1,n,1,tmp,1);

                   }

                }
            }
            l=v[i].l-1;
            v[i].res=query(1,n,1,v[i].l,v[i].r);

        }
        sort(v.begin(),v.end(),cmp2);
        for(int i=0;i<q;i++)
        {
            printf("%d\n",v[i].res);
        }
        for(int i=1;i<=n;i++)
        {
            G[arr[i]].clear();

        }



    }
    return 0;

}


Measured memory_bytes: 46044