#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10, M = 1e6 + 10;
int w[N], res[M];
int cnt[M], ct[M];
int len;
int n, m;
int ans;
struct node
{
    int id, l, r;
} que[M];
int read()
{
    char x;
    while ((x = getchar()) > '9' || x < '0')
        ;
    int u = x - '0';
    while ((x = getchar()) <= '9' && x >= '0')
        u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];
inline void write(int i)
{
    int p = 0;
    if (i == 0)
        p++;
    else
        while (i)
        {
            buf[p++] = i % 10;
            i /= 10;
        }
    for (int j = p - 1; j >= 0; j--)
        putchar('0' + buf[j]);
}

int get(int x)
{
    return x / len;
}
bool cmp(const node &a, const node &b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j)
        return i < j;
    if (i & 1)
        return a.r < b.r;
    else
        return a.r > b.r;
}
void add(int x, int &res)
{
    if (res == cnt[x])
    {
        res++;
    }
    ct[cnt[x]]--;
    cnt[x]++;
    ct[cnt[x]]++;
}
void del(int x, int &res)
{
    if (res == cnt[x] && ct[cnt[x]] == 1)
    {
        res--;
    }
    ct[cnt[x]]--;
    cnt[x]--;
    ct[cnt[x]]++;
}
int main()
{
    n = read();
    m = read();
    vector<int> v;
    for (int i = 1; i <= n; i++)
        w[i] = read(), v.push_back(w[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++)
        w[i] = lower_bound(v.begin(), v.end(), w[i]) - v.begin();
    len = max((int)sqrt(double(1ll * n * n) / m), 1);

    for (int i = 1; i <= m; i++)
    {
        que[i].id = i;
        que[i].l = read(), que[i].r = read();
    }
    sort(que + 1, que + m + 1, cmp);
    for (int k = 1, i = 0, j = 1; k <= m; k++)
    {
        int id = que[k].id, l = que[k].l, r = que[k].r;
        while (i < r)
            add(w[++i], ans);
        while (i > r)
            del(w[i--], ans);
        while (j < l)
            del(w[j++], ans);
        while (j > l)
            add(w[--j], ans);
        res[id] = ans;
    }
    for (int i = 1; i <= m; i++)
        cout << -res[i] << "\n";
    return 0;
}