// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
	inline char gc(void)
	{
		static char buf[100000], *p1 = buf, *p2 = buf;
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
	}

	#define gc() getchar()

	template <class T> inline void read(T &x)
	{
		T flag = (T) 1; x = 0; static char ch = gc();
		for (; ch > '9' || ch < '0'; ch = gc())
			flag = ch == '-' ? -1 : 1;
		for (; ch >= '0' && ch <= '9'; ch = gc())
			x = (x << 1) + (x << 3) + (ch & 15);
		x *= flag; return;
	}

	inline void readstr(string&x) {
		x = ""; static char ch;
		while (isspace(ch = gc()));
		while (x += ch, !isspace(ch = gc()));
	}

	inline void readstr(char *s) {
		do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
		do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
		*s = 0; return;
	}

	inline void printstr(string x, int num = 0, char ch = '\n') {
		for (int i = num; i < x.size(); ++i)
			putchar(x[i]); putchar(ch);
	}

	inline void readch(char&x) { while (isspace(x = gc())); }

	char pf[100000], *o1 = pf, *o2 = pf + 100000;
	#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
	template <class T>
	inline void println(T x, char c = '\n') {
		if (x < 0) ot(45), x = -x;
		static char s[15], *b; b = s;
		if (!x) *b ++= 48;
		for (; x; * b ++= x % 10 + 48, x /= 10);
		for (; b-- != s; ot(*b)); ot(c);
	}

	template <class T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0'); return;
	}

	template <class T> inline void writeln(T x) { write(x); puts(""); }
	template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
	template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

	template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
	template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
	template <class T> inline T max(const T&x, const T&y, const T&z) {
		return x > y ? (x > z ? x : z) : (y > z ? y : z);
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef long double ld;

	#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
	#define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
	#define Mp(x, y) make_pair(x, y)

	inline void file(string str) {
		freopen((str + ".in").c_str(), "r", stdin);
		freopen((str + ".out").c_str(), "w", stdout);
	}

	struct Vector {
		double x, y;
		Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

		inline Vector Vary(void) { return Vector(x, -y); }

		inline bool operator < (const Vector&rhs)
		const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
		inline Vector operator - (const Vector&rhs)
		const { return Vector(x - rhs.x, y - rhs.y); }
		inline Vector operator + (const Vector&rhs)
		const { return Vector(x + rhs.x, y + rhs.y); }

		inline Vector operator * (const double&rhs)
		const { return Vector(x * rhs, y * rhs); }
		inline Vector operator / (const double&rhs)
		const { return Vector(x / rhs, y / rhs); }

		inline Vector operator * (const Vector&rhs)
		const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
	}; typedef Vector Complex;
}

using namespace Base;

const int Maxn = 2e5 + 5;
const int Maxm = 2e5 + 5;
int n, m, t, ret = 0, bel[Maxn], a[Maxn], h[Maxn], sum[Maxn], ans[Maxn];
struct Query {
	int l, r, idx;
	Query(void) { l = r = idx = 0; }
	inline void Scanner(int i) { idx = i; read(l), read(r); }
	inline bool operator < (const Query&rhs) const {
		return (bel[l] == bel[rhs.l]) ? ((r < rhs.r) == (bel[l] & 1)) : (l < rhs.l);
	}
} q[Maxm];

inline void add(int x) { x = a[x]; sum[h[x]]--; h[x]++; sum[h[x]]++; chkmax(ret, h[x]); }
inline void del(int x) { x = a[x]; if (sum[h[x]] == 1 && ret == h[x]) ret--;  sum[h[x]]--; h[x]--; sum[h[x]]++; }

signed main(void) {
//	file("");
	read(n), read(m); t = (int) sqrt(n);
	for (int i = 1; i <= n; i++) read(a[i]), a[i] += 1e5, bel[i] = (i - 1) / t + 1;
	for (int i = 1; i <= m; i++) q[i].Scanner(i); sort(q + 1, q + m + 1);
	int l = 1, r = 1; h[a[1]]++; sum[1]++; ret = 1;
	for (int i = 1; i <= m; i++) {
		while (l < q[i].l) del(l++);
		while (l > q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (r > q[i].r) del(r--);
		ans[q[i].idx] = ret;
	} for (int i = 1; i <= m; i++) writeln(ans[i]);
//	fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

/**/