#include<iostream>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)

#define rep1(i,e) for(int i=1;i<=(e);i++)

#define repx(i,x,e) for(int i=(x);i<=(e);i++)

#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

#define scd(a) scanf("%d",&a)

#define scdd(a,b) scanf("%d%d",&a,&b)

#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define pd(a) printf("%d\n",a)

#define scl(a) scanf("%lld",&a)

#define scll(a,b) scanf("%lld%lld",&a,&b)

#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

#define IOS ios::sync_with_stdio(false);cin.tie(0)

#define lc idx<<1

#define rc idx<<1|1

#define rson mid+1,r,rc

#define lson l,mid,lc

using namespace std;

typedef long long ll;

template <class T>

void test(T a) {

    cout<<a<<endl;

}

template <class T,class T2>

void test(T a,T2 b) {

    cout<<a<<" "<<b<<endl;

}

template <class T,class T2,class T3>

void test(T a,T2 b,T3 c) {

    cout<<a<<" "<<b<<" "<<c<<endl;

}

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const ll mod = 1e9+;

int T;

void testcase() {

    printf("Case %d: ",++T);

}

const int MAXN = 2e5+;

const int MAXM = ;

const double PI = acos(-1.0);

const double eps = 1e-;

struct node{

    int l,r,id;

    bool operator <(const node &b)const{

        return r<b.r;

    }

}Q[MAXN];

int n,q;

int bit[MAXN],a[MAXN],ans[MAXN];

int last[MAXN];

int lowbit(int x){ return x&-x; }

void update(int x,int d){

    while(x<=n){

        bit[x]+=d;

        x+=lowbit(x);

    }

}

int query(int x){

    int res=;

    while(x>){

        res+=bit[x];

        x-=lowbit(x);

    }

    return res;

}

int query(int l,int r){

    return query(r)-query(l-);

}

int main() {

#ifdef LOCAL

    freopen("data.in","r",stdin);

#endif // LOCAL

    while(~scdd(n,q)){

        for(int i=;i<=n;i++) scd(a[i]),a[i+n]=a[i];

        for(int i=;i<q;i++){

            scdd(Q[i].l,Q[i].r);

            Q[i].id=i;

            Q[i].l+=n;

            swap(Q[i].l,Q[i].r);

        }

        n<<=;

        sort(Q,Q+q);

        mset(last,);

        mset(bit,);

        int k=;

        for(int i=;i<=n&&k<q;i++){

            if(last[a[i]]) update(last[a[i]],-);

            last[a[i]]=i;

            update(last[a[i]],);

            while(k<q&&Q[k].r<=i){

                ans[Q[k].id]=query(Q[k].l,Q[k].r);

                k++;

            }

        }

        for(int i=;i<q;i++){

            printf("%d\n",ans[i]);

        }

    }

    return ;

}