#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define VI vector<int>
#define VL vector<ll>
#define MX vector<VI >
#define all(x) x.begin(), x.end()
#define IOS cin.tie(0)->sync_with_stdio(0)

using namespace std;

const int B = 600;

#define jar array<int, 4>
#define jr array<int, 2>

const int N = 1<<19;

int main(){

	IOS;

	int n, q;
	cin >> n >> q;

	VI a(n), h(n+1, 0), am(n+1, 0), ans(q);
	for(int &i : a) cin >> i;

	vector<jar > o(q);

	for(int i=0; i<q; i++){
		int l, r;
		cin >> l >> r;
		o[i] = {l/B, r-1, l-1, i};
	}

	sort(all(o));
	
	int l=0, r=0, mx = 1;
	h[a[0]] = 1;
	am[1] = 1;

	for(jar &i : o){
		while(l > i[2]){
			l--;
			am[h[a[l]]]--;
			h[a[l]]++;
			am[h[a[l]]]++;
			mx = max(mx, h[a[l]]);
		}
		while(r < i[1]){
			r++;
			am[h[a[r]]]--;
			h[a[r]]++;
			am[h[a[r]]]++;
			mx = max(mx, h[a[r]]);
		}
		while(l < i[2]){
			am[h[a[l]]]--;
			if(mx == h[a[l]] && am[h[a[l]]] == 0) mx--;
			h[a[l]]--;
			am[h[a[l]]]++;
			mx = max(mx, h[a[l]]);
			l++;
		}
		while(r > i[1]){
			am[h[a[r]]]--;
			if(mx == h[a[r]] && am[h[a[r]]] == 0) mx--;
			h[a[r]]--;
			am[h[a[r]]]++;
			mx = max(mx, h[a[r]]);
			r--;
		}

		ans[i[3]] = 1+max(0, mx-(i[1]-i[2]+1-mx+1));
	}

	for(int i : ans) cout << i << '\n';

	return 0;
}
