求调

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node {
	int l, r, id;
};
vector<node> q;
int n, m, a[N], ans[N];
int cnt[N], res, temp;
inline void add(int x) {
	++cnt[a[x]];
	while (cnt[res]) ++res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		q.push_back({l, r, i});
	}
	int b = max(pow(n, 0.5L), 1.0L);
	sort(q.begin(), q.end(), [&](auto x, auto y) {
		if (x.l / b != y.l / b) return x.l < y.l;
		return x.r < y.r;
	});
	for (int i = 0; i < m; ) {
		for (int j = 0; j <= 2e5; ++j) cnt[j] = 0;
		temp = 0;
		res = 0;
		int l = min((q[i].l / b + 1) * b, n), r = l - 1;
		do {
			if (q[i].l / b == q[i].r / b) {
				int sum = 0;
				for (int j = q[i].l; j <= q[i].r; ++j) ++cnt[a[j]];
				while (cnt[sum]) ++sum;
				ans[q[i].id] = sum;
				for (int j = q[i].l; j <= q[i].r; ++j) --cnt[a[j]];
			}
			while (r < q[i].r) add(++r);
			temp = res;
			while (l > q[i].l) add(--l);
			ans[q[i].id] = res;
			res = temp;
			while (l < min((q[i].l / b + 1) * b, n)) {
				--cnt[a[l]];
				++l;
			}
			++i;
		} while (q[i].l / b == q[max(i - 1, 0)].l / b);
	}
	for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
	return 0;
}