//https://codeforces.com/problemset/problem/1514/D
//离线思路可以参考https://www.luogu.com.cn/blog/nizhuan/solution-p3709
/**
 * 设[l,r]的长度为len,众数个数为cnt,那么非众数个数x=len-cnt.
 * x个非众数可以和x+1个众数放在一起,满足条件,
 * 多出来的众数只能一个一个放了,个数为cnt-(x+1).
 * 因此需要的总个数为cnt-(len-cnt+1)+1=cnt*2-len.
 * 利用莫队求区间众数
 **/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 2e6 + 100;

struct Question
{
  int l, r, qid;
}Q[N];

int arr[N], res[N], cnt[N], cnt1[N];
int n, q, blo,ans;

bool cmp(const Question &a, const Question &b)
{
    if ((a.l - 1) / blo  == (b.l - 1) / blo) return a.r < b.r;
    return (a.l - 1) / blo  < (b.l - 1) / blo ;
    // if(a.l/blo!=b.l/blo)return a.l<b.l;
    // return a.r<b.r;
}

void add(int x) 
{
    cnt[arr[x]]++;
    cnt1[cnt[arr[x]]]++;
    if (cnt[arr[x]] > ans) ans = cnt[arr[x]];
}

void del(int x) 
{
    /**
        删除操作要考虑删掉的 x 出现次数是不是会影响答案。
        分类讨论
        1. 当出现次数小于当前 ans ，对答案没有影响；
        2.当出现次数等于当前 ans ，且只有这个数出现了 ans 次， ans 减一；
        3.当出现次数等于当前 ans ，且不止一个数出现了 ans 次，对答案没有影响。
    **/
    if (cnt1[cnt[arr[x]]] == 1 && ans == cnt[arr[x]]) ans--;
    cnt1[cnt[arr[x]]]--;
    cnt[arr[x]]--;
}

void Solve()
{
    int l = 1, r = 0;
    sort(Q + 1, Q + q + 1, cmp);
    for (int i = 1; i <= q; i++) {
        while (l > Q[i].l) add(--l);
        while (r < Q[i].r) add(++r);
        while (l < Q[i].l) del(l++);
        while (r > Q[i].r) del(r--);
        int len = Q[i].r - Q[i].l + 1;
        int t = (len + 1) / 2;
        if (ans <= t) res[Q[i].qid] = 1;
        else res[Q[i].qid] = 2 * ans - len;
    }
    for (int i = 1; i <= q; i++) cout << res[i] << endl;
}


int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= q; i++) {
        cin >> Q[i].l >> Q[i].r;
        Q[i].qid = i;
    }
    Solve();
    return 0;
}