// O(M(sqrt N + log M))
#include <bits/stdc++.h>
using namespace std;
class LazySegmentTree {
using S = int;
const S e = -1;
S op(const S &l, const S &r) {
return max(l, r);
}
using F = pair<bool, int>;
const F id = {false, 0};
F composition(const F &g, const F &f) {
return (g.first ? g : f);
}
S mapping(const F &f, const S &x) {
return (f.first ? f.second : x);
}
int n, log;
vector<S> d;
vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < n) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id;
}
public:
LazySegmentTree(int _n) {
log = 0;
while ((1 << log) < _n) log++;
n = 1 << log;
d.assign(2 * n, e);
lz.assign(n, id);
}
S prod(int l, int r) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
for (int i = log; i >= 1; i--) {
if ((l >> i) << i != l) push(l >> i);
if ((r >> i) << i != r) push(r >> i);
}
S res = e;
while (l < r) {
if (l & 1) res = op(res, d[l++]);
if (r & 1) res = op(res, d[--r]);
l >>= 1, r >>= 1;
}
return res;
}
void apply(int l, int r, F f) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
for (int i = log; i >= 1; i--) {
if ((l >> i) << i != l) push(l >> i);
if ((r >> i) << i != r) push(r >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1, r >>= 1;
}
l = l2, r = r2;
}
for (int i = 1; i <= log; i++) {
if ((l >> i) << i != l) update(l >> i);
if ((r >> i) << i != r) update(r >> i);
}
}
};
class IncrementalIntervalScheduling {
int n, b, num;
map<int, int> mp;
vector<int> L, to, cnt;
void update_block(int id) {
assert(0 <= id and id < num);
int l = id * b, r = (id + 1) * b;
for (int i = r - 1; i >= l; i--) {
int nx, g;
if (L[i] == -1) {
nx = i + 1, g = 0;
} else {
nx = L[i], g = 1;
}
if (nx < r) {
to[i] = to[nx];
cnt[i] = cnt[nx] + g;
} else {
to[i] = nx;
cnt[i] = g;
}
}
}
public:
IncrementalIntervalScheduling(int n) : n(n) {
b = clamp((int) sqrt(n), 1, n);
num = (n + 1 + b - 1) / b;
L.assign(b * num, -1);
to.resize(b * num);
cnt.resize(b * num);
for (int i = 0; i < num; i++) update_block(i);
}
void reset() {
for (auto [l, r]: mp) {
L[l] = -1;
update_block(l / b);
}
mp.clear();
}
void add(int l, int r) {
assert(0 <= l and l < r and r <= n);
auto it = mp.lower_bound(l);
if (it == mp.end() or it->second > r) {
mp[l] = r;
L[l] = r;
update_block(l / b);
it = mp.find(l);
while (it != mp.begin()) {
--it;
if (it->second < next(it)->second) break;
L[it->first] = -1;
update_block(it->first / b);
it = mp.erase(it);
}
}
}
int interval_scheduling() {
int now = 0, res = 0;
while(now < n) {
res += cnt[now];
now = to[now];
}
return res;
}
};
class IntervalManager {
int n;
vector<int> r_ls;
map<int, int> mp;
public:
vector<int> build(vector<pair<int, int>> ls, int _n) {
n = _n;
sort(ls.begin(), ls.end(), [](auto a, auto b) { return a.second < b.second; });
int now = -(1 << 30);
for (auto [l, r]: ls) {
if (mp.contains(l)) mp[l] = min(mp[l], r);
else mp[l] = r;
if (now > l) continue;
now = r;
r_ls.push_back(r);
}
assert((int) r_ls.size() == n);
if (mp.empty()) return r_ls;
auto it = prev(mp.end());
while (it != mp.begin()) {
--it;
if (it->second >= next(it)->second) {
it = mp.erase(it);
}
}
return r_ls;
}
// returns the list of pairs of (old_val, new_val)
vector<pair<int, int>> add(int l, int r) {
// update mp
{
auto it = mp.lower_bound(l);
if (it == mp.end() or it->second > r) {
mp[l] = r;
it = mp.find(l);
while (it != mp.begin()) {
--it;
if (it->second < next(it)->second) break;
it = mp.erase(it);
}
}
}
vector<pair<int, int>> res;
// update r_ls
{
auto it = lower_bound(r_ls.begin(), r_ls.end(), r);
while (it != r_ls.end()) {
int lb = (it == r_ls.begin() ? -(1 << 30) : *prev(it));
int nr = mp.lower_bound(lb)->second;
assert(nr <= *it);
if (nr == *it) break;
res.emplace_back(*it, nr);
*it = nr;
it++;
}
}
return res;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<int> c(n);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
++c[--a];
}
IncrementalIntervalScheduling iis(n);
int frontier = n - 1;
LazySegmentTree st(n);
vector<pair<int, int>> ls;
vector<IntervalManager> lm(n), rm(n);
while (m--) {
int l, r;
cin >> l >> r;
--l;
int mx = st.prod(l, r);
if (mx == -1) {
while (!c[frontier]) --frontier;
cout << frontier + 1 << '\n';
iis.add(l, r);
ls.emplace_back(l, r);
if (iis.interval_scheduling() == c[frontier]) {
vector<int> nr = lm[frontier].build(ls, c[frontier]);
for (int i = 0; i < (int) ls.size(); i++) {
auto [x, y] = ls[i];
ls[i] = {-y, -x};
}
vector<int> nl = rm[frontier].build(ls, c[frontier]);
reverse(nl.begin(), nl.end());
for (int &i: nl) i = -i;
for (int i = 0; i < c[frontier]; i++) {
assert(nl[i] < nr[i]);
st.apply(nl[i], nr[i], {true, frontier});
}
ls.clear();
iis.reset();
--frontier;
}
} else {
cout << mx + 1 << '\n';
for (auto [pre, now]: lm[mx].add(l, r)) {
st.apply(now, pre, {true, -1});
}
for (auto [pre, now]: rm[mx].add(-r, -l)) {
st.apply(-pre, -now, {true, -1});
}
}
}
}
