求优化 $O(qn\log n)$ 做法或提供正解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;

class fastio
{
	static const int MAX = 1 << 15; char ibuf[MAX], *p1 = ibuf, *p2 = ibuf, obuf[MAX], *p3 = obuf, sta[50]; bool file_end = false;
	char get() { return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, MAX, stdin), p1 == p2) ? (file_end = true), char(EOF) : *p1++; }
	void put(const char x) { p3 - obuf < MAX ? *p3++ = x : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x); }
	explicit operator bool() { return !file_end; }
	size_t flush() { size_t f = fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; *p3 = 0; return f; }
public :
	fastio &operator >> (char &t) { for (t = get(); !isgraph(t); t = get()); return *this; }
	fastio &operator >> (char *t) { char c; for (c = get(); !isgraph(c); c = get()); for (; isgraph(c); c = get()) * t = c, t++; *t = 0; return *this; }
	fastio &operator >> (string &t) { t.clear(); char c; for (c = get(); !isgraph(c); c = get()); for (; isgraph(c); c = get()) t += c; return *this; }
	fastio &operator << (const char t) { put(t); return *this; }
	fastio &operator << (const char *t) { for (; *t; ++t) put(*t); return *this; }
	fastio &operator << (const string &t) { for (const char it : t) put(it); return *this; }
	fastio &read(char *t) { char c; for (c = get(); !isgraph(c); c = get()); for (; isgraph(c); c = get()) * t = c, t++; *t = 0; return *this; }
	template <typename any1, typename any2> pair<any1, any2> tpval() { return pair<any1, any2>(tpval<any1>(), tpval<any2>()); }
	template <typename any> typename enable_if <is_same<any, char>::value, any>::type tpval() { char t; for (t = get(); !isgraph(t); t = get()); return t; }
	template <typename any> typename enable_if <is_same<any, string>::value, any>::type tpval() { string t; char c; for (c = get(); !isgraph(c); c = get()); for (; isgraph(c); c = get()) t += c; return t; }
	template <typename any> typename enable_if <(is_signed<any>::value && is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __int128_t>::value, any >::type tpval() { any t = 0; bool y = 0; char c = get(); for (; !isdigit(c); c = get()) if (c == 45) y = true; for (; isdigit(c); c = get()) t = t * 10 + c - 48; if (y == 1) t = -t; return t; }
	template <typename any> typename enable_if <(is_signed<any>::value && std::is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __int128_t>::value, fastio >::type &operator >> (any &t) { t = 0; bool y = 0; char c = get(); for (; !isdigit(c); c = get()) if (c == 45) y = true; for (; isdigit(c); c = get())t = t * 10 + c - 48; if (y == 1) t = -t; return *this; }
	template <typename any> typename enable_if <(is_unsigned<any>::value && std::is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __uint128_t>::value, any >::type tpval() { any t = 0; char c = get(); for (; !isdigit(c); c = get()); for (; isdigit(c); c = get()) t = t * 10 + c - 48; return t; }
	template <typename any> typename enable_if <(is_unsigned<any>::value && is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __uint128_t>::value, fastio >::type &operator >> (any &t) { t = 0; char c = get(); for (; !isdigit(c); c = get()); for (; isdigit(c); c = get()) t = t * 10 + c - 48; return *this; }
	template <typename any1, typename any2> fastio &operator >> (pair<any1, any2> &t) { return *this >> t.first >> t.second; }
	template <typename any> typename enable_if <(is_signed<any>::value && is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __int128_t>::value, fastio >::type &operator << (any t) { if (!t) { put(48); return *this; } int len = 0; if (t < 0) t = -t, put(45); while (t) sta[len++] = char(t % 10 + 48), t /= 10; while (len--) put(sta[len]); return *this; }
	template <typename any> typename enable_if <(is_unsigned<any>::value && is_integral<any>::value && !is_same<any, char>::value) || is_same<any, __uint128_t>::value, fastio >::type &operator << (any t) { if (!t) { put(48); return *this; } int len = 0; while (t) sta[len++] = char(t % 10 + 48), t /= 10; while (len--) put(sta[len]); return *this; }
	template <typename any1, typename any2> fastio &operator << (const pair<any1, any2> &t) { return *this << t.first << ' ' << t.second; } template <typename any> fastio &write(const any &t) { return *this << t; } template <typename any, typename...args> fastio &write(const any &t1, const args &...t2) { return (*this << t1).write(t2...); }
	template <typename any> fastio &read(any &t) { return *this >> t; }
	template <typename any, typename...args> fastio & read(any &t1, args &...t2) { return (*this >> t1).read(t2...); }
	~fastio() { fwrite(obuf, p3 - obuf, 1, stdout); }
} fio;

const int N = 1e6 + 5;
int n, q, m, l, r, a[N], b[N], cnt[N];
vector<int> vec[N];
map<pair<int, int>, int> ans;

int get(int x) {
	int ans = n + 1;
	for (int i = 0; i <= n; ++i) {
		int siz = vec[i].size();
		for (int j = 0, k = 0, t = vec[i][j], ned = max(x * 2, t - l + 1) + t;
			j < siz && vec[i].back() >= ned && t <= r; ++j, t = vec[i][j], ned = max(x * 2, t - l + 1) + t) {
			if (t < l) continue;
			while (vec[i][k] < ned) ++k;
			if (vec[i][k] > r) break;
			ans = min(ans, vec[i][k] - t);
			if (ans == x * 2) return ans;
		}
	}
	return ans;
}

int solve() {
	int p = 0, res = 0;
	while (p <= (r - l + 1) / 2) {
		int t = get(p);
		// cout << p << '\n';
		if (t <= (r - l + 1) / 2) {
			p = t;
			++res;
		} else break;
	}
	return res;
}

int main() {
	fio >> n >> q;
	for (int i = 1; i <= n; ++i) {
		fio >> a[i];
		vec[a[i]].push_back(i);
	}
	for (int i = 0; i <= n; ++i) vec[i].push_back(n + 1);
	for (int i = 1; i <= q; ++i) {
		fio >> l >> r;
		if (ans.count(make_pair(l, r))) fio << ans[make_pair(l, r)] << '\n';
		else fio << (ans[make_pair(l, r)] = solve()) << '\n';
	}
	return 0;
}