#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<deque>
#include<utility>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 3e5 + 5;
const int BLOCK = 550;

int ar[N];
int cnt[N];
int freq[N];
int cur = 0;

struct query{
  int l, r, idx;
};

bool cmp(query a, query b){
    int blocka = a.l/BLOCK;
    int blockb = b.l/BLOCK;
    if(blocka == blockb)return a.r < b.r;
    return blocka < blockb;
}

void add(int x){
    --freq[cnt[ar[x]]];
    ++freq[++cnt[ar[x]]];
    cur = max(cur, cnt[ar[x]]);
}

void del(int x){
    --freq[cnt[ar[x]]];
    ++freq[--cnt[ar[x]]];
}

int ans[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> ar[i];
    
    vector<query> lst;
    for(int i = 1; i <= q; ++i){
        int l, r; cin >> l >> r;
        lst.pb({l, r, i}); 
    }

    for(int i = 1; i <= n; ++i)++freq[0];

    sort(lst.begin(), lst.end(), cmp);
    
    int l = 0, r = -1;
    
    for(int i = 0; i < lst.size(); ++i){
        int curl = lst[i].l;
        int curr = lst[i].r;
        
        while(r < curr) add(++r);
        while(r > curr) del(r--);
        
        while(l < curl) del(l++);
        while(l > curl) add(--l);

        while(freq[cur] == 0)--cur;

        int rg = curr - curl + 1;
        ans[lst[i].idx] = max(2*cur - rg, 1);
    }
    
    for(int i = 1; i <= q; ++i){
        cout << ans[i] << endl;
    }
	return 0;
}
