#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, INF = 0x3f3f3f3f;
int cnt[N], num[N], a[N], res[N];
int n, m, kuai;
struct rt {
    int id;
    int l, r;
} que[N];
bool cmp(rt a, rt b) {
    if (a.l / kuai == b.l / kuai) return a.r < b.r;
    return a.l / kuai < b.l / kuai;
}
int ans[N];
signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    kuai = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) {
        cin >> que[i].l >> que[i].r;
        que[i].id = i + 1;
    }
    sort(que, que + m, cmp);
    int ma = -INF;
    int l = 1, r = 0;
    for (int i = 0; i < m; i++) {
        while (l < que[i].l) {
            num[cnt[a[l]]]--;
            if (ma == cnt[a[l]] && !num[cnt[a[l]]]) {
                ma = cnt[a[l]] - 1;
            }
            cnt[a[l]]--;
            num[cnt[a[l]]]++;
            l++;
        }
        while (r < que[i].r) {
            ++r;
            num[cnt[a[r]]]--;
            cnt[a[r]]++;
            num[cnt[a[r]]]++;
            if (ma < cnt[a[r]]) ma = cnt[a[r]];
        }
        while (l > que[i].l) {
            --l;
            num[cnt[a[l]]]--;
            cnt[a[l]]++;
            num[cnt[a[l]]]++;
            if (ma < cnt[a[l]]) ma = cnt[a[l]];
        }
        while (r > que[i].r) {
            num[cnt[a[r]]]--;
            if (ma == cnt[a[r]] && !num[cnt[a[r]]]) {
                ma = cnt[a[r]] - 1;
            }
            cnt[a[r]]--;
            num[cnt[a[r]]]++;
            r--;
        }
        res[i] = ma;
    }
    for (int i = 0; i < m; i++) {
        int id = que[i].id;
        int len = que[i].r - que[i].l + 1, num = res[i];
        int l = 1, r = num;
        while (l < r) {
            int mid = l + r >> 1;

            int upnum = (num + mid - 1) / mid;
            int lownum = num / mid;
            if (upnum == lownum) {
                int upcnt = 0;
                int remainlen = len / mid;
                if (remainlen >= 2 * upnum - 1)
                    r = mid;
                else
                    l = mid + 1;
            } else {
                int fenzi = num - lownum * mid;
                int fenmu = upnum - lownum;
                int upcnt = 0;
                if (fenmu != 0) upcnt = fenzi / fenmu;
                int lowlen = lownum * 2 - 1;
                int remainlen = (len - (mid - upcnt) * lowlen) / upcnt;
                if (remainlen >= 2 * upnum - 1)
                    r = mid;
                else
                    l = mid + 1;
            }
        }
        ans[id] = l;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
    return 0;
}