#include<bits/stdc++.h>
using namespace std;
int n,q,l=1,r,smax,ans[300005],bel[300005],a[300005],ap[300005],in[300005];
struct Node{int l,r,id;}s[300005];
bool cmp(Node x,Node y){
    if(bel[x.l]!=bel[y.l])  return bel[x.l]<bel[y.l];
    if(bel[x.l]&1)    return x.r<y.r;
    return x.r>y.r;
}
void add(int x){ap[in[a[x]]++]--,smax=max(smax,in[a[x]]),ap[in[a[x]]]++;}
void del(int x){
    if(!(--ap[in[a[x]]])&&in[a[x]]==smax)   smax--;
    ap[--in[a[x]]]++;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)   scanf("%d",a+i);
    int bl=sqrt(n);
    for(int i=1;i<=n;i++)   bel[i]=(i-1)/bl;
    for(int i=1,x,y;i<=q;i++)   scanf("%d%d",&x,&y),s[i]={x,y,i};
    sort(s+1,s+q+1,cmp);
    for(int i=1;i<=q;i++){
        while(l<s[i].l) del(l++);
        while(l>s[i].l) add(--l);
        while(r<s[i].r) add(++r);
        while(r>s[i].r) del(r--);
        ans[s[i].id]=max(1,smax*2-r+l-1);
    }
    for(int i=1;i<=q;i++)   printf("%d\n",ans[i]);
}