    #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3e5+5;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> V(n+1);
    vector<vector<int>> pos(maxn);
    for(int i=1;i<=n;i++) {cin>>V[i];pos[V[i]].push_back(i);}
    while(m--){
        int l,r;cin>>l>>r;
        int cnt=0;
        for(int i=1;i<=30;i++) {
            int rd=V[uniform_int_distribution<int>(l,r)(rng)];
            int lb=lower_bound(pos[rd].begin(),pos[rd].end(),l)-pos[rd].begin(),
                rb=upper_bound(pos[rd].begin(),pos[rd].end(),r)-pos[rd].begin();
            if((rb-lb)>(r-l)/2+1) {
                cnt=rb-lb;break;
            }
        }
        if(cnt==0) {cout<<1<<endl;continue;}
        int left=(r-l+1)-cnt;
        cout<<cnt-left<<endl;
    }
	return 0;
}