#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 1e5 + 100;
typedef long long ll;

int n, a[maxn];
int q;
int block[maxn];
int cnt[maxn];
int cnt_dif;

struct Query
{
    int l, r, id;
    int ans;
} querys[maxn];

bool cmp(const Query & x, const Query & y)
{
    if (block[x.l] == block[y.l]) return x.r < y.r;
    return x.l < y.l;
}
bool cmp_id(const Query & x, const Query & y)
{
    return x.id < y.id;
}

void update(int p, int add)
{
    if (add == -1)
    {
        if (cnt[a[p]] == 1) --cnt_dif;
        cnt[a[p]]--;
    }
    else
    {
        if (cnt[a[p]] == 0) ++cnt_dif;
        cnt[a[p]]++;
    }
}


int main()
{
    while (scanf("%d%d", &n, &q) == 2)
    {
        memset(cnt, 0, sizeof(int)*(1+n));
        cnt_dif = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", a + i);
            if (cnt[a[i]] == 0) ++cnt_dif;
            cnt[a[i]]++;
        }
        int block_size = (int)sqrt(n);
        for (int i = 1; i <= n; ++i)
            block[i] = (i - 1) / block_size + 1;
        for (int i = 1; i <= q; ++i)
        {
            scanf("%d%d", &querys[i].l, &querys[i].r);
            if(querys[i].l >= querys[i].r) querys[i].r = querys[i].l+1;
            querys[i].id = i;
        }

        sort(querys + 1, querys + 1 + q, cmp);

        int l = 1, r = 2;
        for (int i = 1; i <= q; ++i)
        {
            for (; r < querys[i].r; ++r) update(r, -1);
            for (; r > querys[i].r; --r) update(r - 1, 1);
            for (; l < querys[i].l; ++l) update(l + 1, 1);
            for (; l > querys[i].l; --l) update(l, 1);
            querys[i].ans = cnt_dif;
        }
        sort(querys + 1, querys + 1 + q, cmp_id);
        for (int i = 1; i <= q; ++i) printf("%d\n", querys[i].ans);
    }

    return 0;
}