#include <bits/stdc++.h>
using namespace std;

const int N = 300 * 1000 + 10;

int n, q, a[N];
vector<int> pos[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int cnt(int l, int r, int x) {
    return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
}

int main() {
    ios:: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> a[i], pos[a[i]].push_back(i);
    int l, r, num;
    while (q--) {
        cin >> l >> r, --l, --r;
        int x = r - l + 2;
        for (int i = 0; i < 40; i++) {
            int pl = rng() % (r - l + 1) + l;
            num = cnt(l, r, a[pl]);
            if (num > x / 2)
                break;
        }
        if (num > x / 2)
            cout << 2 * num - x + 1 << '\n';
        else
            cout << "1\n";
    }
}
