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

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define trav(a, x) for(auto& a:x)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define f first
#define s second
#define nl "\n"
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MOD=1e9+7;
template<class T> using pqg=priority_queue<T, vector<T>, greater<T>>;

int n, q;
int a[300001];
int l[300001];
int r[300001];
int freq[300001];
vi query[561];
int num[300001];

bool comp(int a, int b){ return r[a]<r[b]; }

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);

  cin >> n >> q;
  rep(i, 1, n) cin >> a[i];

  int M=(int)sqrt(n);
  rep(i, 1, q){
    cin >> l[i] >> r[i];
    query[l[i]/M].pb(i);
  }

  rep(k, 0, n/M){
    sort(all(query[k]), comp);
    int mx=0;
    vi freq(n+1);
    int last=(k+1)*M-1;
    rep(i, 0, sz(query[k])-1){
      int x=query[k][i];
      if(r[x]<(k+1)*M){
        rep(j, l[x], r[x]){
          freq[a[j]]++;
          num[x]=max(num[x], freq[a[j]]);
        }
        rep(j, l[x], r[x]){
          freq[a[j]]--;
        }
        continue;
      }
      while(last<r[x]){
        last++;
        freq[a[last]]++;
        mx=max(mx, freq[a[last]]);
      }
      num[x]=mx;
      rep(j, l[x], (k+1)*M-1){
        freq[a[j]]++;
        num[x]=max(num[x], freq[a[j]]);
      }

      rep(j, l[x], (k+1)*M-1){
        freq[a[j]]--;
      }
    }
  }

  rep(i, 1, q){
    int len=r[i]-l[i]+1;
    if(num[i]<=(len-1)/2+1) cout << 1 << nl;
    else{
      int x=len-num[i];
      cout << num[i]-x << nl;
    }
  }
}