#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>
using namespace std;
const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;
int n , q , a[maxn];
vector <int> bit[maxn];
void update(int id , int val)
{
int idx = id;
while(idx <= n)
{
bit[idx].push_back(val);
idx += (idx & (-idx));
}
}
int getp(int p , int val)
{
int idx = p;
int res = 0;
while(idx > 0)
{
res += (int)(lower_bound(bit[idx].begin() , bit[idx].end() , val) - bit[idx].begin());
idx -= (idx & (-idx));
}
return res;
}
int get_ask(int l , int r , int val)
{
return (r - l + 1) - (getp(r , val) - getp(l-1 , val));
}
void solve()
{
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) update(i , a[i]);
for(int i = 1; i <= n; i++)
{
sort(bit[i].begin() , bit[i].end());
}
while(q--)
{
int L , R , H = -1; cin >> L >> R;
int l = 1 , r = (R - L + 1);
while(l <= r)
{
int mid = (l + r)/2;
if(get_ask(L , R , mid) >= mid)
{
H = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << H << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
