RT

#include <bits/stdc++.h>

#define int long long
#define LL long long
#define ULL unsigned long long
#define I ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int N = 2e5 + 5, M = 5e7 + 2;

using namespace std;

const int mod = 998244353, inf = 0x3f3f3f3fll;

int n, q;

int Root[N], idx;

int Sum[N << 5], L[N << 5], R[N << 5];

int build(int l, int r)
{
	int rt = ++ idx;
	Sum[rt] = 0;
	if (l < r)
	{
		int mid = (l + r) >> 1;
		L[rt] = build(l, mid);
		R[rt] = build(mid + 1, r);
	}
	return rt;
}

int Update(int Prt, int l, int r, int val)
{
	int rt = ++ idx;
	L[rt] = L[Prt], R[rt] = R[Prt], Sum[rt] = Sum[Prt] + 1;
	if (l < r)
	{
		int mid = (l + r) >> 1;
		if (val <= mid) L[rt] = Update(L[Prt], l, mid, val);
		else R[rt] = Update(R[Prt], mid + 1, r, val);
	}
	return rt;
}

int Qry(int x, int y, int l, int r, int k)
{
	if (l >= r) return l;
	int s = Sum[L[y]] - Sum[L[x]];
	int mid = (l + r) >> 1;
	if (s >= k) return Qry(L[x], L[y], l, mid, k);
	else return Qry(R[x], R[y], mid + 1, r, k - s);
}

signed main()
{
	I;
	
	cin >> n >> q;
	Root[0] = build(1, n);
	for (int i = 1; i <= n; i ++ )
	{
		int x;
		cin >> x;
		Root[i] = Update(Root[i - 1], 1, n, x);
	}
	while (q -- )
	{
		int x, y;
		cin >> x >> y;
		int L = 1, R = n;         
		while (L < R)
		{
			int mid = (L + R + 1) >> 1;// h
			//cout << x << ' ' << y << ' ' << mid << '\n';
			//cout << Qry(Root[y], Root[x - 1], 1, n, (n - mid + 1)) << '\n';
			if (((y - x + 1) >= mid) && Qry(Root[y], Root[x - 1], 1, n, (n - mid + 1)) >= mid) L = mid;
			else R = mid - 1;
		}
		cout << L << '\n';
	}
	//n = 5
	//1 2 3 4 5
	//k = 2
	// 
}

//Segment Tree