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

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = a, _b = b; i <= _b; ++i) 
#define FORD(i, a, b) for(int i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).begin(), (a).end()
#define MASK(i) (1ll<<(i))
typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***End of Template***/
int n, q;
const int N = 3e5+5;
vi pos[N];
int a[N];

void Input() {
	cin >> n >> q;
	FOR(i, 1, n) {
		cin >> a[i];
		pos[a[i]].pb(i);
	}
}

int cnt(int v, int l, int r) {
	return upper_bound(ALL(pos[v]), r) - lower_bound(ALL(pos[v]), l);
}

void Solve() {
	while (q--) {
		int l, r; cin >> l >> r;
		int mx = 0;
		FOR(_, 1, 40) {
			int v = a[int(rand()*rand())%(r-l+1) + l];
			mx = max(cnt(v, l, r), mx);
		}
		cout << max(1, 2*mx - (r-l+1)) << '\n';
	}
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    Input(); Solve();
    return 0;
}