#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;
#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
vector<vector<int>> st;
vector<int> vec;
void query(int root, int left, int right, int qLeft, int qRight)
{
if (left>qRight || right<qLeft) return;
if (left>=qLeft && right<=qRight) {
vec.push_back(root);
return;
}
int mid=(left+right)/2;
query(root*2, left, mid, qLeft, qRight);
query(root*2+1, mid+1, right, qLeft, qRight);
}
void build(int root, int left, int right, vector<int>& v)
{
if (left==right) {
st[root].push_back(v[left]);
return;
}
int mid=(left+right)/2;
build(root*2, left, mid, v);
build(root*2+1, mid+1, right, v);
st[root]=st[root*2];
st[root].insert(st[root].end(), all(st[root*2+1]));
sort(all(st[root]));
return;
}
int n, q;
vector<int> a;
void solve() {
cin >> n >> q;
a.clear(), a.resize(n);
for (auto &u: a) cin >> u;
st.resize(4*n);
build(1, 0, n-1, a);
while (q--) {
int ll, rr; cin >> ll >> rr;
ll--, rr--;
int l=0, r=rr-ll+1;
int ans=0;
vec.clear();
query(1, 0, n-1, ll, rr);
while (l<=r) {
int mid=(l+r)/2;
int sum=0;
for (auto &u: vec) {
sum+=st[u].end()-lower_bound(all(st[u]), mid);
}
if (sum>=mid) {
ans=mid;
l=mid+1;
} else {
r=mid-1;
}
}
cout << ans << endl;
}
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
return 0;
}
