/********   All Required Header Files ********/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;

/****** Template of some basic operations *****/
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
/**********************************************/;

struct SegmentTree {
    uint32 n;
    uint32 **t;
    vector<uint32> *c;

    SegmentTree(uint32 size) {
        n = size;
        t = new uint32*[2 * n];
        REP(i, 2 * n) t[i] = new uint32[3];

        c = new vector<uint32>[n];
    }

    void build() {
        uint32 l, r, vl, vr;
        for (uint32 i = n - 1; i > 0; --i) {
            vl = t[i<<1][0];
            vr = t[i<<1|1][0];
            l = min(t[i<<1][1], t[i<<1|1][1]);
            r = max(t[i<<1][2], t[i<<1|1][2]);
            // printf("i=%d, vl=%d, vr=%d, l=%d, r=%d\n", i, vl, vr, l, r);
            t[i][0] = count(vl, l, r) > count(vr, l, r) ? vl : vr;
            t[i][1] = l;
            t[i][2] = r;
            // printf("Result: (%d, %d, %d)\n", t[i][0], t[i][1], t[i][2]);
        }
    }

    uint32 query(uint32 l, uint32 r) {
        uint32 lo = l, hi = r - 1;
        uint32 resl = 0, resr = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) resl = max(resl, count(t[l++][0], lo, hi));
            if (r&1) resr = max(count(t[--r][0], lo, hi), resr);
            // printf("l=%d, r=%d, resl=%d, resr=%d\n", l, r, resl, resr);
        }
        return max(resl, resr);
    }

    uint32 count(uint32 target, uint32 l, uint32 r) {
        target--;
        return upper_bound(c[target].begin(), c[target].end(), r) - lower_bound(c[target].begin(), c[target].end(), l);
    }
};

void solve() {
    uint32 n, q;
    SCLD(n); SCLD(q);

    SegmentTree st = SegmentTree(n);
    // printf("Done creating tree\n");
    REP(i, n) {
        SCLD(st.t[n + i][0]);
        st.t[n + i][1] = i; st.t[n + i][2] = i;
        st.c[st.t[n + i][0] - 1].PB(i);
    }
    // printf("Done reading\n");
    st.build();
    // printf("Done building\n");
    // REP(i, 2*n) printf("(%d, %d, %d) ", st.t[i][0], st.t[i][1], st.t[i][2]);
    // printf("\n");

    int32 l, r, f;
    REP(i, q) {
        SCLD(l); SCLD(r); l--;
        f = st.query(l, r);
        // printf("f=%d\n", f);
        printf("%ld\n", max((int32)1, 2 * f - (r - l)));
    }
}

int main() {
    int t = 1; 
    // SCD(t);
    while (t--) {
        solve();
    }
}