///?
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <string>
#include <iomanip>
#include <utility>
//#include <conio.h> C++14 upper
#include <limits.h>
#include <random>  //mt19937
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <queue> //priority queue
#include <time.h>  //clock_t
#include <deque>
#define ll long long
#define taskname ""
#define faster ios_base::sync_with_stdio(false);\
cin.tie(nullptr);
#define debug(x) cout<<x<<". ";
#define debug1(a,n) for (int i=0;i<n;++i) cout<<a[i]<<":) ";
#define debug2(d,m,n) for (int i=0;i<m;++i){\
                        for (int j=0;j<n;++j) cout<<a[i][j]<<":)) ";\
                        cout<<"\n";\
                      }
#define min(a,b) ((a>b)?b:a)
#define max(a,b) ((a>b)?a:b)
#define ceil(a,b) ((a%b==0)?a/b:a/b+1)
using namespace std;

const int Mod = 1000000007;
const int maxN = 3e5 + 1;
int tt, n, q, l , r;
int a[maxN];
vector <int> b[maxN];
mt19937 Rand(time(0));
void Solve(){
    while (q--){
        cin >> l >> r;
        --l;--r;
        int maxx = 0;
        for (int i = 1; i <= 30; ++i){
            int val = a[l + Rand() % (r - l + 1)];
            maxx = max(maxx, upper_bound(b[val].begin(), b[val].end(), r) - lower_bound(b[val].begin(), b[val].end(), l));
        }
        cout << max(2*maxx + l - r - 1,1) <<"\n";
    }
}

void Init(){
    cin >> n >> q;
    for (int i=0;i<n;++i){
        cin >> a[i];
        b[a[i]].push_back(i);
    }
}

int main(){
    faster
    //freopen(taskname".INP","r",stdin);
    //freopen(taskname".OUT","w",stdout);
    Init();
    Solve();
}
