#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define maxn 100005
using namespace std;
int cnt[maxn], cc[maxn], a[maxn];
int cur = 0;
struct que{
    int l, r, k, ind;
    que(int a, int b, int c, int d) {
        l = a, r = b, k = c, ind = d;
    }
    que() {
        l = 0, r = 0, k = 0, ind = 0;
    }
};
bool cmp(que a, que b) {
    return a.r < b.r;
}
void add(int ind) {
    cc[cnt[a[ind]]]--;
    cnt[a[ind]]++;
    cc[cnt[a[ind]]]++;
    cur = max(cur, cnt[a[ind]]);
}
void del(int ind) {
    cc[cnt[a[ind]]]--;
    cnt[a[ind]]--;
    cc[cnt[a[ind]]]++;
    if (cc[cur] == 0) cur--;
}
int main() {
    int n, q;
    cin >> n >> q;
    int ans[q];
    int block = int(ceil(sqrt(n)));
    for (int i = 0;i < n;i++) cin >> a[i], a[i]--;
    vector<que> v[block];
    for (int i = 0;i < q;i++) {
        int l, r, k;
        cin >> l >> r;
        l--, r--;
        v[l / block].push_back(que(l, r, 0, i));
    }
    int curl = 0, curr = -1;
    cc[0] = n;
    for (int i = 0;i < block;i++) {
        sort(v[i].begin(), v[i].end(), cmp);
        for (auto j:v[i]) {
            while (curr < j.r) {
                curr++;
                add(curr);
            }
            while (curl > j.l) {
                curl--;
                add(curl);
            }
            while (curr > j.r) {
                del(curr);
                curr--;
            }
            while (curl < j.l) {
                del(curl);
                curl++;
            }
            //for (int k = 0;k <= cur;k++) cout << cc[k] << " ";
            //cout << endl;
            //ans[j.ind] = (cur * j.k >= j.r - j.l + 1 ? 1 : 0);
            ans[j.ind] = cur;
        }
    }
    for (int i = 0;i < q;i++) cout << ans[i] << "\n";

}