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

typedef long long ll;
#define re(n) cin >> n
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
#define ff(i,x,n) for(int i=(int)x;i<(int)n;i++)
#define f(i,n) ff(i,0,n)
#define ffi(i, n, x) for(int i=(int)n; i>=(int)x; i--)
#define fi(i, n) ffi(i, n, 0)
#define rea(a) f(i, (sizeof a/sizeof a[0])){ re(a[i]); }
#define rev(a) f(i, a.size()){ re(a[i]); }
#define puta(a) f(i, (sizeof a/sizeof a[0])){ cout << a[i] << " "; } cout << "\n"
#define putv(a) f(i, a.size()){ cout << a[i] << " "; } cout << "\n"
#define fast std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define te(t) int t; re(t); while(t--)
#define mod 1000000007

#ifdef LOCAL
	#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template < typename Arg1 >
	void __f(const char* name, Arg1&& arg1){
	    cout << name << " = " << arg1 << std::endl;
	}
	template < typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args){
		const char* comma = strchr(names+1, ',');
		cout.write(names, comma - names) << " = " << arg1 <<" - ";
		__f(comma+1, args...);
	}
#else
	#define debug(...)
#endif

const int BLK = 555;
const int N = 300005;

struct query {
	int l;
	int r;
	int in;
	bool operator<(query other) const
    {
        return make_pair(l / BLK, r) < make_pair(other.l / BLK, other.r);
    }
};

int a[N], fr[N]={0}, frfr[N]={0}, ans[N], anss = 0;
query qs[N];

void add_sd(int pos){
	frfr[fr[a[pos]]]--;
	fr[a[pos]]++;
	frfr[fr[a[pos]]]++;
	anss = max(fr[a[pos]], anss);
}

void remove_sd(int pos){
	frfr[fr[a[pos]]]--;
	fr[a[pos]]--;
	frfr[fr[a[pos]]]++;
	if(fr[a[pos]] < anss){
		while(frfr[anss] == 0)
			anss--;
	}
}

int main(){
	fast;
	int n, t;
	re(n >> t);
	f(i, n) re(a[i]);
	f(i, t){
		int l, r;
		re(l >> r);
		l--;
		r--;
		qs[i].l = l;
		qs[i].r = r;
		qs[i].in = i;
	}
	sort(qs, qs+t);
	int CL = 0, CR = -1;
	f(i, t){
		while(CL > qs[i].l){
			CL--;
			add_sd(CL);
		}
		while(CR < qs[i].r){
			CR++;
			add_sd(CR);
		}
		while(CL < qs[i].l){
			remove_sd(CL);
			CL++;
		}
		while(CR > qs[i].r){
			remove_sd(CR);
			CR--;
		}
		int total = qs[i].r - qs[i].l + 1;
		int rem = total - anss;
		// cout << rem << " / " << total << " " << qs[i].l << "-" << "" <<"\n";
		if(anss <= ((total/2)+(total%2)))
			ans[qs[i].in] = 1;
		else{
			ans[qs[i].in] = total - 2*rem;
		}
	}
	f(i, t){
		cout << ans[i] << "\n";
	}
	return 0;
}