/* -> Written by <-
   -----------
  |K_A_Z_A_M_A|
  |___________|
  |    ___    |
  |   (^_^)   |
  |  /( | )\  |
  |____|_|____|
    H O A N G
*/

#include <bits/stdc++.h>

#define Task            "running"
#define F               first
#define S               second
#define pb              push_back
#define bit(x, i)       ((x >> (i)) & 1)
#define inf             1e9 + 7
#define INF             1e18 + 7
#define ll              long long
#define pii             pair <int, int>
#define debug(x)        cerr << #x << " is " << x << "\n";

using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int base = 3e5 + 1;

int n, q;
int a[300005];
vector <int> p[300005];

void Solve(int test_case) {
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        p[a[i]].pb(i);
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i <= q; ++ i) {
        int l, r; cin >> l >> r;
        int ans = 1;
        for (int times = 1; times <= 40; ++ times) {
            int u = a[uniform_int_distribution<int>(l,r)(rng)];
            int f = upper_bound(p[u].begin(), p[u].end(), r) - lower_bound(p[u].begin(), p[u].end(), l);
            ans = max(ans, 2 * f - (r - l + 1));
        }
        cout << ans << "\n";
    }
}


int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
//    Prepare();
    int test_case = 1;
//     cin >> test_case;
    for (int i = 1; i <= test_case; ++ i) {
        Solve(i);
    }
    return 0;
}
