#include <bits/stdc++.h> // very  important question of randomization 
// and important concept of binary search...
// could also be done with mo's algorithm.....
using namespace std;
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}


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

void solve(){
	int n,q;
	cin >> n >> q;
	
	vector<int> a(n+1);
	vector<vector<int>> id(n+1);
	rep(i,1,n+1){
		cin >> a[i];
		id[a[i]].pb(i);
	}
	
	for(int y=0;y<q;y++){
		int l,r;
		cin >> l >> r;
		auto dist=uniform_int_distribution<int>(l,r);
		//set<int> vals;
        vector<int> vals;
       // cout<<"the random are "<<endl;  // here 22 is not enough because
       // resubmitting again and again the same solution 
       // we found out that sometimes the same solution gets AC 
       // and sometimes it gets WA on some of the test cases...
		for(int i=0;i<40;i++){
			int p = dist(rng);
			vals.push_back(a[p]);
		}
		sort(vals.begin(), vals.end());
   vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
		int mx = 0;
		for(int x:vals){
			int f = upper_bound(all(id[x]),r) - lower_bound(all(id[x]),l);
            amax(mx,f);
		}
		int wid = r - l + 1;
        // int cl=(wid+1)/2;
        // if(mx<=cl)
        // {
        //     cout<<1<<endl;
        // }
        // else
        // {
        //     int u=2*mx-wid;
        //     cout<<u<<endl;
        // }
		// very important observation about binary search
		// here and in template...
        // or use binary search to find  the max  elements which can be used 
		int L = 0, U = mx;
        while(L < U){
			int m = (U+L) / 2;
			int a = wid - m;
			int b = mx - m;
			int allowed = (a + 1) / 2;
			if(allowed >= b){
				U = m;
			}
			else{
				L = m+1 ;
			}
		}
		U++;
		cout << U << "\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
   #endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}
