#pragma GCC optimize("O2")

#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define fi first
#define se second
#define mpa make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
mt19937 gen(time(0));

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<int> c(n + 1);
    int k = 800;
    int K = (n + k - 1) / k * 2;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ++c[a[i]];
    }
    vector<int> d;
    for (int i = 0; i <= n; ++i) if (c[i] >= K) d.eb(i);
    vector<vector<int>> psum(d.size(), vector<int>(n + 1, 0));
    for (int i = 0; i < (int)(d.size()); ++i) {
        for (int j = 1; j <= n; ++j) {
            psum[i][j] = psum[i][j - 1] + (a[j - 1] == d[i]);
        }
    }
    vector<int> temp(n + 1);
    for (int z = 0; z < q; ++z) {
        int l, r;
        cin >> l >> r;
        int mx = 0;
        if (r - l + 1 < k) {
            for (int j = l - 1; j < r; ++j) {
                ++temp[a[j]];
                mx = max(mx, temp[a[j]]);
            }
            for (int j = l - 1; j < r; ++j) --temp[a[j]];
        } else {
            for (int j = 0; j < (int)(d.size()); ++j) {
                int cnt = psum[j][r] - psum[j][l - 1];
                mx = max(mx, cnt);
            }
        }
        int len = (r - l + 1);
        int L = 0, R = mx;
        while (L != R) {
            int M = (L + R) / 2;
            if ((len - M + 1) / 2 >= mx - M) {
                R = M;
            } else {
                L = M + 1;
            }
        }
        cout << R + 1 << '\n';
    }
}
/*

*/
