#include<bits/stdc++.h>
using namespace std;
const int N = (int) 5e5 + 5;
struct query
{
    int l,r,id;
} q[N];
int a[N],k=1000,l=1,r=0;

bool compare(query &a,query &b)
{
    int b_a = a.l/k;
    int b_b = b.l/k;
    if(b_a==b_b)
        return a.r<b.r;

    return b_a<b_b;
}
int cnt[N],ans[N];
int res=0;
void add(int x)
{
    cnt[a[x]]++;
    if(cnt[a[x]]==1)
        ++res;
}
void remove(int x)
{
    cnt[a[x]]--;
    if(cnt[a[x]]==0)
        --res;
}

int main()
{
    int n,Q;
    cin>>n>>Q;
    for(int i=1; i<=n; ++i)
        cin>>a[i];
    for(int i=1; i<=Q; ++i)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+Q+1,compare);
    for(int i=1; i<=Q; ++i)
    {
        while(l > q[i].l)
            add(--l);
        while(r < q[i].r)
            add(++r);
        while(l < q[i].l)
            remove(l++);
        while(r > q[i].r)
            remove(r--);
        ans[q[i].id]=res;
    }

    for(int i=1; i<=Q; ++i)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}

