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

#define no printf("No\n")
#define yes printf("Yes\n")
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ERAGE(x) x.erase(unique(all(x)), x.end())

void files()
{
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    return;
}
typedef long long ll;

const int MXN = 3e5 + 5;
const long long MOD = 1e9 + 7;
int sq;
int cnt[MXN];
int fre[MXN];
struct ID
{
    int l;
    int r;
    int ind;
    bool operator<(const ID &other) const
    {
        int own = l / sq;
        int her = other.l / sq;
        if (own == her)
        {
            if (own & 1)
                return r > other.r;
            else
                return r < other.r;
        }
        else
            return own < her;
    }
};
void sol()
{
    int n, q;
    scanf("%d %d", &n, &q);
    sq = sqrt(n);
    int x[n];
    ID id[q];
    for (int i = 0; i < n; ++i)
        scanf("%d", &x[i]);
    for (int i = 0; i < q; ++i)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        --l;
        --r;
        id[i].l = l;
        id[i].r = r;
        id[i].ind = i;
    }
    sort(id, id + q);
    int mx = 0;
    int ans[q];
    int cur_l = 0;
    int cur_r = -1;
    for (int i = 0; i < q; ++i)
    {
        int l = id[i].l;
        int r = id[i].r;

        while (cur_l > l)
        {
            cur_l--;
            if (fre[cnt[x[cur_l]]] > 0 && cnt[x[cur_l]] > 0)
                fre[cnt[x[cur_l]]]--;
            cnt[x[cur_l]]++;
            fre[cnt[x[cur_l]]]++;
            mx = max(mx, cnt[x[cur_l]]);
        }
        while (cur_r < r)
        {
            cur_r++;
            if (fre[cnt[x[cur_r]]] > 0 && cnt[x[cur_r]] > 0)
                fre[cnt[x[cur_r]]]--;
            cnt[x[cur_r]]++;
            fre[cnt[x[cur_r]]]++;
            mx = max(mx, cnt[x[cur_r]]);
        }
        while (cur_l < l)
        {
            fre[cnt[x[cur_l]]]--;
            if (fre[cnt[x[cur_l]]] == 0 && cnt[x[cur_l]] == mx)
                --mx;
            cnt[x[cur_l]]--;
            fre[cnt[x[cur_l]]]++;
            cur_l++;
            mx = max(0, mx);
        }
        while (cur_r > r)
        {
            fre[cnt[x[cur_r]]]--;
            if (fre[cnt[x[cur_r]]] == 0 && cnt[x[cur_r]] == mx)
                --mx;
            cnt[x[cur_r]]--;
            fre[cnt[x[cur_r]]]++;
            cur_r--;
            mx = max(0, mx);
        }
        int sum = r - l + 1;
        if ((sum + 1) / 2 >= mx)
            ans[id[i].ind] = 1;
        else
            ans[id[i].ind] = mx - (sum - mx);
    }
    for (int i = 0; i < q; ++i)
        printf("%d\n", ans[i]);
}
int main()
{
    //files();
    int tcase = 1;
    //scanf("%d", &tcase);
    while (tcase--)
    {
        sol();
    }
}
