#include <iostream>
#include <vector>
using namespace std;
// Space dimension strictly fitted for N <= 400
int min_R[405][405];
int main() {
// Optimize standard I/O operations for performance
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> A(N);
vector<int> counts(N + 1, 0);
for (int i = 0; i < N; ++i) {
cin >> A[i];
counts[A[i]]++;
}
// Identify all uniquely present "beauty" values in ascending order
vector<int> u;
for (int i = 1; i <= N; ++i) {
if (counts[i] > 0) u.push_back(i);
}
int K = u.size();
vector<int> C(K, 0);
for (int i = 0; i < K; ++i) {
int c = 0;
for (int j = u[i]; j <= N; ++j) {
c += counts[j];
}
C[i] = c; // C[i] captures count of paintings >= u[i]
}
// Initialize all interval-end bounds loosely
for (int i = 0; i < K; ++i) {
for (int p = 1; p <= N; ++p) {
min_R[i][p] = N + 1;
}
}
for (int j = 0; j < M; ++j) {
int L_j, R_j;
cin >> L_j >> R_j;
int v_fail = -1;
for (int i = 0; i < K; ++i) {
// Fast skip if the new requirement doesn't tighten the existing constraints
if (R_j >= min_R[i][L_j]) continue;
int points = 0;
int cur_min_R = N + 1;
const int* mR_arr = min_R[i];
int c_i = C[i];
// Evaluate stabbing points needed if the new interval gets introduced
for (int p = 1; p < L_j; ++p) {
int mR = mR_arr[p];
if (mR < cur_min_R) cur_min_R = mR;
if (p == cur_min_R) {
points++;
if (points > c_i) goto check_fail;
cur_min_R = N + 1;
}
}
{ // Process specific updated location isolated branching dynamically
int p = L_j;
int mR = mR_arr[p];
if (R_j < mR) mR = R_j;
if (mR < cur_min_R) cur_min_R = mR;
if (p == cur_min_R) {
points++;
if (points > c_i) goto check_fail;
cur_min_R = N + 1;
}
}
for (int p = L_j + 1; p <= N; ++p) {
int mR = mR_arr[p];
if (mR < cur_min_R) cur_min_R = mR;
if (p == cur_min_R) {
points++;
if (points > c_i) goto check_fail;
cur_min_R = N + 1;
}
}
check_fail:
if (points > c_i) {
v_fail = i;
break;
}
}
// Output Maximum permissible threshold fallback
int ans_idx = (v_fail == -1) ? K - 1 : v_fail - 1;
cout << u[ans_idx] << "\n";
// Commit modifications permanently up to validated capacity
for (int i = 0; i <= ans_idx; ++i) {
if (R_j < min_R[i][L_j]) {
min_R[i][L_j] = R_j;
}
}
}
return 0;
}
