#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
#define int ll
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define raya cerr << "==================" << endl;
#define fore(i, a, b) for(int i=a; i<b; ++i)
const int N = 2e5+5;
int p[N], n, q;
int mp[N];
struct Node {
Node *left, *right;
int val;
Node() {
left = nullptr;
right = nullptr;
val = 0;
}
};
int arr[N];
Node* version[N];
void init(Node *cur, int tl, int tr){
if(tl == tr){
cur->val = arr[tl];
return;
}
int tm = (tl + tr) / 2;
cur->left = new Node();
cur->right = new Node();
init(cur->left, tl, tm);
init(cur->right, tm+1, tr);
cur->val = cur->left->val + cur->right->val;
}
void update(Node *cur, Node *prev, int tl, int tr, int idx, int val){
if(tl == tr){
arr[tl] = val;
cur->val = val;
return;
}
int tm = (tl + tr) / 2;
if(idx <= tm){
cur->left = new Node();
cur->right = prev->right;
update(cur->left, prev->left, tl, tm, idx, val);
} else {
cur->left = prev->left;
cur->right = new Node();
update(cur->right, prev->right, tm+1, tr, idx, val);
}
cur->val = cur->left->val + cur->right->val;
}
void update(Node *cur, Node *prev, int idx, int val){
update(cur, prev, 0, N-1, idx, val);
}
int query(Node *cur, int tl, int tr, int l, int r){
if(l <= tl && tr <= r){
return cur->val;
}
if(r < tl or tr < l){
return 0;
}
int tm = (tl + tr) / 2;
int p1 = query(cur->left, tl, tm, l, r);
int p2 = query(cur->right, tm+1, tr, l, r);
return p1 + p2;
}
int query(Node *cur, int l, int r){
return query(cur, 0, N-1, l, r);
}
signed main(){
cin >> n >> q;
fore(i, 0, n){
cin >> p[i];
}
version[0] = new Node();
init(version[0], 0, N);
fore(i, 0, n){
version[i+1] = new Node();
int prevVal = query(version[i], p[i], p[i]);
update(version[i+1], version[i], p[i], prevVal + 1);
}
fore(i, 0, q){
int l, r;
cin >> l >> r;
int low = 1, high = N;
int res = -1;
while(low <= high){
int mid = low + (high - low) / 2;
int cnt = query(version[r], mid, N-1) - query(version[l-1], mid, N-1);
if(cnt >= mid){
res = mid;
low = mid+1;
} else {
high = mid-1;
}
}
cout << res << endl;
}
}
