#include <bits/stdc++.h>
using namespace std;
int N , Q , arr[300000+10] , ans[300000+10];
int cnt[300000+10] , freq[300000+10];
int maxi , block = 700 ;
struct Node
{
    int L ,R ,id ;
    bool operator < (const Node &A) const
    {
        if(L/block == A.L/block) return R < A.R ;
        else return L/block < A.L/block ;
    }
}input[300000+10];
void add(int index)
{
    if(index==0) return ;
    if(cnt[arr[index]]!=0) freq[cnt[arr[index]]]--;
    cnt[arr[index]]++;
    freq[cnt[arr[index]]]++;
    if(cnt[arr[index]]>maxi) maxi = cnt[arr[index]] ;
}

void remove(int index)
{
    if(index==0) return ;
    freq[cnt[arr[index]]]--;
    if(freq[maxi]==0) maxi--;
    cnt[arr[index]]--;
    if(cnt[arr[index]]!=0)freq[cnt[arr[index]]]++;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int N,Q;
    cin>>N>>Q;
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&arr[i]);
        }
        int diff[Q+1];
        for(int i=1;i<=Q;i++)
        {
            scanf("%d%d",&input[i].L,&input[i].R);
            input[i].id = i ;
            diff[i]=input[i].R-input[i].L;
            diff[i]++;
        }
        sort(input+1,input+Q+1);
        int currentL = 0 , currentR = 0 ;
        for(int i=1;i<=Q;i++)
        {
            int L = input[i].L , R = input[i].R ;
            while( currentL < L ) remove(currentL++);
            while( currentL > L ) add(--currentL) ;
            while( currentR < R ) add(++currentR);
            while( currentR > R ) remove(currentR--);
            ans[input[i].id] = maxi ;
        }
        for(int i=1;i<=Q;i++){
        	int tmp=diff[i]-ans[i];
        	cout<<max(1,ans[i]-tmp)<<"\n";
        }
    return 0;
}