#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
	if (S == T) {
		T = (S = buf) + fread(buf, 1, SIZE, stdin);
		if (S == T) return '\n';
	}
	return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
	fwrite(buf, 1, S - buf, stdout);
	S = buf;
}
inline void putchar(char c) {
	*S++ = c;
	if (S == T) flush();
}
struct NTR {
	~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
	template<typename T>
	Reader& operator >> (T& x) {
		char c = getchar();
		T f = 1;
		while (c < '0' || c > '9') {
			if (c == '-') f = -1;
			c = getchar();
		}
		x = 0;
		while (c >= '0' && c <= '9') {
			x = x * 10 + (c - '0');
			c = getchar();
		}
		x *= f;
		return *this;
	}
	Reader& operator >> (char& c) {
		c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		return *this;
	}
	Reader& operator >> (char* str) {
		int len = 0;
		char c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
			str[len++] = c;
			c = getchar();
		}
		str[len] = '\0';
		return *this;
	}
	Reader(){}
} cin;
const char endl = '\n';
struct Writer {
	template<typename T>
	Writer& operator << (T x) {
		if (x == 0) { putchar('0'); return *this; }
		if (x < 0) { putchar('-'); x = -x; }
		static int sta[45];
		int top = 0;
		while (x) { sta[++top] = x % 10; x /= 10; }
		while (top) { putchar(sta[top] + '0'); --top; }
		return *this;
	}
	Writer& operator << (char c) {
		putchar(c);
		return *this;
	}
	Writer& operator << (char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer& operator << (const char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;
const int N = 5e5 + 10;
ll n, q, a[N], b[N], l[N], r[N], ans[N], flag = 1;
set<pii>st;
void solve()
{
	pii flag = {n + 1, n + 1};
	st.insert(flag);
	for (int i = 1; i <= n; i ++ )
	{
		int u = a[i];
		if (ans[i - 1] > u) b[ans[i - 1]] ++ ;
		else
		{
			auto it = st.upper_bound({u, 0});
			if (*it == flag) st.insert({u, u}), b[u] = 1;
			else
			{
				it -- ; auto x = *it;
				if (x.second < u) st.insert({u, u}), b[u] = 1;
				else
				{
					st.erase(it);
					st.insert({x.first - 1, x.second});
					b[x.first - 1] ++ ;
				}
			}
			it = st.lower_bound({u, 0});
			auto it1 = it; it -- ;
			auto v = *it, u = *it1;
			if (u.first == v.second + 1)
			{
				st.erase(v); st.erase(u);
				st.insert({v.first, u.second});
			}
		}
		ans[i] = ans[i - 1];
		while (b[ans[i]]) ans[i] ++ ;
	}
	for (int k = 1; k <= q; k ++ ) cout << ans[r[k]] << endl;
}
int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i <= q; i ++ ) cin >> l[i] >> r[i], flag = flag & (l[i] == 1);
	if (flag && n * q > 5e8) solve();
//	else if (n * q > 5e8) solve2();
	else
	{
		for (int k = 1; k <= q; k ++ )
		{
			ll m = r[k] - l[k] + 1;
			for (int i = 0; i <= min(n, m * 2); i ++ ) b[i] = 0;
			for (int j = l[k]; j <= r[k]; j ++ ) b[a[j]] ++ ;
			for (int i = min(n, m * 2); i > 0; i -- )
			{
				if (b[i] == 0) continue;
				b[i - 1] += b[i] - 1;
				b[i] = 1;
			}
			for (int i = 0; i <= m; i ++ )
			{
				if (b[i] == 0)
				{
					cout << i << endl;
					break;
				}
				else b[i + 1] += b[i] - 1, b[i] = 1;
			}
		}
	}
	cerr << "Time : " << clock() << " ms\n";
	return 0;
}