#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=3e5+5;
const int LIM=30;
const int LOG=18;

int n, q;
int p[N];
vector <int> v[N];

int cnt(int x, int l, int r) {
    return upper_bound(v[x].begin(), v[x].end(), r)-lower_bound(v[x].begin(), v[x].end(), l);
}

int random(int lo, int hi) {
    int ret=0;
    for (int i=0; i<LOG; ++i) ret+=(1<<i)*(rand()%2);
    return ret%(hi-lo+1)+lo;
}

int main() {
    srand(42069);
    scanf("%d %d", &n, &q);
    for (int i=0; i<n; ++i) {
        scanf("%d", &p[i]);
        v[p[i]].pb(i);
    }
    for (int e=0; e<q; ++e) {
        int l, r;
        scanf("%d %d", &l, &r); l--; r--;
        int maxi=0, d=r-l+1;
        for (int i=0; i<LIM && maxi<(d+1)/2; ++i) {
            int x=random(l, r);
            maxi=max(maxi, cnt(p[x], l, r));
        }
        int ost=d-maxi;
        if (maxi>(d+1)/2) printf("%d\n", ost+maxi-2*ost);
        else printf("1\n");
    }
	return 0;
}
