#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int N = 1e5 + 5;
int n, m;
pair<int, int> segment[N];
set<int> st[4 * N];
int mx[N];
void update(int id, int l, int r, int u, int v, int x) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
st[id].insert(x);
mx[id] = max(mx[id], x);
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, x);
update(id * 2 + 1, mid + 1, r, u, v, x);
mx[id] = max({mx[id], mx[id * 2], mx[id * 2 + 1]});
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) {
return mx[id];
}
int mid = (l + r) / 2;
int ret = 0;
if (!st[id].empty()) ret = *st[id].rbegin();
return max(ret, max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)));
}
void era(int id, int l, int r, int u, int v, int x) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
if (st[id].find(x) != st[id].end()) st[id].erase(st[id].find(x));
mx[id] = 0;
if (!st[id].empty()) mx[id] = *st[id].rbegin();
if (l != r) mx[id] = max({mx[id], mx[id * 2], mx[id * 2 + 1]});
return;
}
int mid = (l + r) / 2;
era(id * 2, l, mid, u, v, x);
era(id * 2 + 1, mid + 1, r, u, v, x);
mx[id] = max({mx[id], mx[id * 2], mx[id * 2 + 1]});
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int best = n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
}
for (int i = 1; i <= m; i++) segment[i] = {1, n};
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
int res = get(1, 1, n, l, r);
if (res == 0) {
res = best;
update(1, 1, n, l, r, best);
segment[res] = {l, r};
best--;
}
else {
era(1, 1, n, segment[res].F, segment[res].S, res);
segment[res] = {max(segment[res].F, l), min(segment[res].S, r)};
update(1, 1, n, segment[res].F, segment[res].S, res);
}
cout << res << '\n';
}
}
