#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to calculate the maximum number of disjoint intervals (Interval Scheduling)
int get_IS(const vector<pair<int, int>>& intervals) {
int count = 0;
int last_R = 0;
// The intervals are expected to be already sorted by their right endpoints (R)
for (const auto& p : intervals) {
// Two intervals [L1, R1] and[L2, R2] are disjoint if L2 > R1
if (p.first > last_R) {
count++;
last_R = p.second;
}
}
return count;
}
int main() {
// Optimize standard I/O operations for competitive programming
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> A(N);
vector<int> C(N + 1, 0); // C[i] will store the number of times beauty 'i' appears in A
for (int i = 0; i < N; ++i) {
cin >> A[i];
C[A[i]]++;
}
// S[i] stores the intervals assigned to beauty value i, sorted by their right endpoints
vector<vector<pair<int, int>>> S(N + 1);
for (int j = 0; j < M; ++j) {
int L, R;
cin >> L >> R;
int chosen_i = -1;
// Greedily try to assign the largest possible beauty value i
for (int i = N; i >= 1; --i) {
if (C[i] == 0) continue;
// Find the correct position to insert the new interval to maintain the sorted order by R
auto it = S[i].begin();
while (it != S[i].end() && (it->second < R || (it->second == R && it->first < L))) {
it++;
}
// Temporarily insert the interval [L, R]
auto inserted_it = S[i].insert(it, {L, R});
// Check if the Interval Scheduling answer is <= count of i
if (get_IS(S[i]) <= C[i]) {
chosen_i = i;
break; // Found the maximum valid i, keep the interval in S[i] and break
} else {
// If not valid, remove the temporarily inserted interval and try the next i
S[i].erase(inserted_it);
}
}
// Output the maximum lexicographical choice for the j-th interval
cout << chosen_i << "\n";
}
return 0;
}
