#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define X first
#define Y second
#define db(x) (cerr << #x << ": " << (x) << '\n')
const int INF = 1000000007;
using namespace std;
int L = 0, R = -1, BS = 550;
int a[300001];
int f[300001];
int fme = 0;
int fof[300001];
void _insert(int x){
    --fof[f[x]];
    ++f[x];
    ++fof[f[x]];
    fme = max(fme, f[x]);
}
void _remove(int x){
    --fof[f[x]];
    --f[x];
    ++fof[f[x]];
    if(!fof[fme])
        --fme;
}
void query(int l, int r){
    // R    r
    while(R < r){
        ++R;
        _insert(a[R]);
    }
    // l    L
    while(L > l){
        --L;
        _insert(a[L]);
    }
    // r    R
    while(R > r){
        _remove(a[R]);
        --R;
    }
    // L   l
    while(L < l){
        _remove(a[L]);
        ++L;
    }
}
bool cmp(tuple<int,int,int>& a, tuple<int,int,int>& b){
    bool res = get<0>(a) / BS != get<0>(b) / BS;
    if(res) return get<0>(a) / BS < get<0>(b) / BS;
    return get<1>(a) < get<1>(b);
}
int32_t main(){  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n, q;
    cin>>n>>q;
    //vector<int> a(n);
    for(int i{}; i < n; ++i){
        cin>>a[i];
    }
    vector<tuple<int,int,int>> vq(q);
    for(int id{}; id < q; ++id){
        int l, r;
        cin>>l>>r;
        vq[id] = tie(l, r, id);
    }
    sort(vq.begin(), vq.end(), cmp);

    vector<int> ans(q);
    for(auto t: vq){
        int l, r, id;
        tie(l, r, id) = t;

        query(l - 1, r - 1);

        if(fme > (r - l + 1) / 2)
            ans[id] = (2 * fme) - (r - l + 1);
        else
            ans[id] = 1;
    }
    for(auto x: ans)
        cout<<x<<endl;

    return 0;
}