#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
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> C(N + 1, 0); // Count occurrences of each beauty value
for (int i = 0; i < N; ++i) {
cin >> A[i];
C[A[i]]++;
}
// Graph components for each beauty value i in [1, N]:
// max_L[i][r] stores the maximum left endpoint 'l' for an interval ending at 'r'
// min_R[i][l] stores the minimum right endpoint 'r' for an interval starting at 'l'
vector<vector<int>> max_L(N + 1, vector<int>(N + 1, -1));
vector<vector<int>> min_R(N + 1, vector<int>(N + 1, INF));
// DP arrays as described in the slides:
// Len0[i][k] = max disjoint intervals in S_i using items in [0, k)
// LenN[i][k] = max disjoint intervals in S_i using items in[k, N)
vector<vector<int>> Len0(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> LenN(N + 1, vector<int>(N + 1, 0));
for (int j = 0; j < M; ++j) {
int L, R;
cin >> L >> R;
// Convert to 0-indexed, half-open interval[l, r)
int l = L - 1;
int r = R;
int chosen_i = -1;
// Greedily try the largest possible beauty value i
for (int i = N; i >= 1; --i) {
if (C[i] == 0) continue;
// Check if the interval can be added without exceeding total occurrences C[i]
if (Len0[i][l] + 1 + LenN[i][r] <= C[i]) {
chosen_i = i;
break;
}
}
cout << chosen_i << "\n";
// Add the interval to S_{chosen_i} and update our tracking arrays
max_L[chosen_i][r] = max(max_L[chosen_i][r], l);
min_R[chosen_i][l] = min(min_R[chosen_i][l], r);
// Recompute Len0[chosen_i] from scratch in O(N)
for (int k = 1; k <= N; ++k) {
Len0[chosen_i][k] = Len0[chosen_i][k - 1]; // simulate length 0 edge: (k-1) -> k
if (max_L[chosen_i][k] != -1) {
// simulate length 1 edge: max_L -> k
Len0[chosen_i][k] = max(Len0[chosen_i][k], Len0[chosen_i][max_L[chosen_i][k]] + 1);
}
}
// Recompute LenN[chosen_i] from scratch in O(N)
for (int k = N - 1; k >= 0; --k) {
LenN[chosen_i][k] = LenN[chosen_i][k + 1]; // simulate length 0 edge: k -> (k+1)
if (min_R[chosen_i][k] != INF) {
// simulate length 1 edge: k -> min_R
LenN[chosen_i][k] = max(LenN[chosen_i][k], 1 + LenN[chosen_i][min_R[chosen_i][k]]);
}
}
}
return 0;
}
