#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
   char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=200010;
struct query
{
    int l,r,bi;
}qs[N];
bool cmp(query x,query y){return x.r<y.r;}
int n,q;
int last[N],a[N],b[N],c[N],res[N];
int nowt;
void add(int w)
{
    if(w==0)
    {
        c[w]++;
        return;
    }
    while(w<=N)
    {
        c[w]++;
        w+=w&-w;
    }
    return;
}
int ans;
int query_seg(int w)
{
    ans=0;
    while(w)
    {
        ans+=c[w];
        w-=w&-w;
    }
    return ans;
}
struct Seg
{
    int l,r,val;
}s[4*N];
void push_up(int p){s[p].val=max(s[p<<1].val,s[p<<1|1].val);}
void build(int l,int r,int p)
{
    s[p]=(Seg){l,r,a[l]};
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    push_up(p);
    return;
}
int qmax(int l,int r,int p)
{
    if(l>r) return 1e9;
    if(l<=s[p].l&&s[p].r<=r) return s[p].val;
    int mid=(s[p].l+s[p].r)/2,z=0;
    if(l<=mid) z=max(z,qmax(l,r,p<<1));
    if(mid<r) z=max(z,qmax(l,r,p<<1|1));
    return z;
}
int main()
{
    freopen("dry.in","r",stdin);
    freopen("dry.out","w",stdout);
    n=re();q=re();
    for(int i=1;i<=n;i++)
    {
        a[i]=re();
        b[i]=last[a[i]];
        last[a[i]]=i;
    }
    build(1,n,1);
    for(int i=1;i<=q;i++) qs[i].l=re(),qs[i].r=re(),qs[i].bi=i;
    sort(qs+1,qs+1+q,cmp);
    for(int i=1;i<=q;i++)
    {
        while(nowt<qs[i].r)
        {
            nowt++;
            if(qmax(b[nowt]+1,nowt-1,1)>a[nowt]) add(b[nowt]);
        }
        res[qs[i].bi]=qs[i].r-qs[i].l+1-query_seg(qs[i].r)+query_seg(qs[i].l-1);
    }
    for(int i=1;i<=q;i++) printf("%d\n",res[i]);
    return 0;
}