#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
#define N 200001
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
int ans[N], l[N], r[N];
const int BL = 450;
int l1, l2;
bool cmp(int &x, int &y)
{
l1 = l[x] / BL;
l2 = l[y] / BL;
if (l1 != l2)
return l1 < l2;
if (l1 & 1)
return r[x] > r[y];
return r[x] < r[y];
}
const int NN = 200001;
int t[NN];
void add(int v)
{
for (; v < NN; v = v | (v + 1))
t[v]++;
}
void del(int v)
{
for (; v < NN; v = v | (v + 1))
t[v]--;
}
int res;
void get(int v)
{
res = 0;
for (; v >= 0; v = (v & (v + 1)) - 1)
res += t[v];
}
int main()
{
istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int n, q, i;
cin >> n >> q;
int a[n];
for (i = 0; i < n; i++)
cin >> a[i];
vector <int> vr; vr.clear();
for (i = 0; i < q; i++)
{
cin >> l[i] >> r[i];
l[i]--; r[i]--;
vr.PB(i);
}
sort(all(vr), cmp);
int ll = 0, rr = -1, all, L, R, md;
for (i = 0; i < sz(vr); i++)
{
while (rr < r[vr[i]])
add(a[++rr]);
while (l[vr[i]] < ll)
add(a[--ll]);
while (r[vr[i]] < rr)
del(a[rr--]);
while (ll < l[vr[i]])
del(a[ll++]);
all = rr - ll + 1;
L = 0; R = all;
while (L < R)
{
md = (L + R + 1) >> 1;
get(md - 1);
if (all - res >= md)
L = md;
else R = md - 1;
}
ans[vr[i]] = L;
}
for (i = 0; i < q; i++)
pri(ans[i]);
}
