#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(), v.end()
#define endl "\n"
void __print(int x){cerr << x;}
void __print(long double x){cerr << x;}
void __print(char x){cerr << '\'' << x << '\'';}
void __print(double x){cerr << x;}
void __print(float x){cerr << x;}
void __print(unsigned int x){cerr << x;}
void __print(bool x){cerr << x;}
void __print(const char *x){cerr << '\"' << x << '"';}
void __print(const string &x){cerr << '\"' << x << '"';}
template<typename T, typename V>
void __print(const pair<T,V>&x){cerr << "{";__print(x.first);cerr<<",";__print(x.second);cerr<<"}";}
template<typename T>
void __print(const T&x){int f = 0;cerr<<"{";for(auto &i:x)cerr<<(f++?",":""),__print(i);cerr<<"}";}
void _print(){cerr << "]\n";}
template<typename T, typename...V>
void _print(T t, V... v){__print(t);if(sizeof...(v))cerr<<",";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...)cerr << "LINE(" << __LINE__ << ") -> [" << #x << "] = [";_print(x);
#else
#define dbg(x...)
#endif
const int mxn = 2e5+5, mxk = 20;
struct pstactive{
vector<pair<int,int>>child;
vector<int>seg;
int ptr = 0, sz = 1;
void init(int n){
while(sz < n)sz*=2;
seg.resize(mxn*mxk);
child.resize(mxn*mxk);
}
void set(int curr, int prev, int lx, int rx, int i, int v){
if(rx-lx==1){
seg[curr] = v;
return;
}
int m = (lx+rx)/2;
if(i < m){
child[curr].first = ++ptr;
child[curr].second = child[prev].second;
set(child[curr].first, child[prev].first, lx,m,i,v);
}else{
child[curr].second = ++ptr;
child[curr].first = child[prev].first;
set(child[curr].second, child[prev].second,m, rx, i, v);
}
seg[curr] = seg[child[curr].first] + seg[child[curr].second];
}
void set(int curr, int prev, int i, int v){
set(curr,prev,0,sz,i,v);
}
int sol(int curr, int lx, int rx, int l, int r){
if(curr==0)return 0;
if(lx >= l && rx <= r)return seg[curr];
if(rx<=l || lx >= r)return 0ll;
int m = (lx+rx)/2;
return sol(child[curr].first,lx,m,l,r)+sol(child[curr].second,m,rx,l,r);
}
int sol(int curr, int l, int r){
return sol(curr,0,sz,l,r);
}
};
struct pstmin{
vector<pair<int,int>>child;
vector<int>seg;
int ptr = 0, sz = 1;
void init(int n){
while(sz < n)sz*=2;
seg.resize(mxn*mxk,1e9);
child.resize(mxn*mxk);
}
void set(int curr, int prev, int lx, int rx, int i, int v){
if(rx-lx==1){
seg[curr] = v;
return;
}
int m = (lx+rx)/2;
if(i < m){
child[curr].first = ++ptr;
child[curr].second = child[prev].second;
set(child[curr].first, child[prev].first, lx,m,i,v);
}else{
child[curr].second = ++ptr;
child[curr].first = child[prev].first;
set(child[curr].second, child[prev].second,m, rx, i, v);
}
seg[curr] = min(seg[child[curr].first], seg[child[curr].second]);
}
void set(int curr, int prev, int i, int v){
set(curr,prev,0,sz,i,v);
}
int sol(int curr, int lx, int rx, int l, int r){
if(curr==0)return 1e9;
if(lx >= l && rx <= r)return seg[curr];
if(rx<=l || lx >= r)return 1e9;
int m = (lx+rx)/2;
return min(sol(child[curr].first,lx,m,l,r),sol(child[curr].second,m,rx,l,r));
}
int sol(int curr, int l, int r){
return sol(curr,0,sz,l,r);
}
};
int a[mxn],rootmin[mxn],rootactive[mxn];
int32_t main(){
int n,k;
cin >> n>> k;
for(int i = 1;i<=n;++i)cin >> a[i];
pstmin pstmn;
pstactive pstact;
pstmn.init(n+1);
pstact.init(n+1);
vector<vector<int>>vals(mxn+1);
for(int i = 1;i<=n;++i)vals[a[i]].pb(i);
int lst = 1;
for(int i = mxn;i>=0;--i){
if(vals[i].empty())continue;
rootmin[lst] = rootmin[lst-1];
for(int v : vals[i]){
int curr = ++pstmn.ptr, prev = rootmin[lst];
pstmn.set(curr,prev,v,i);
rootmin[lst] = curr;
}
rootactive[lst] = rootactive[lst-1];
for(int v : vals[i]){
int curr = ++pstact.ptr, prev = rootactive[lst];
pstact.set(curr,prev,v,1);
rootactive[lst] = curr;
}
lst++;
}
while(k--){
int L, R;
cin >> L >> R;
int l = 1, r = lst-1;
int res = 0;
while(l <= r){
int m = (l+r)/2;
int x = pstact.sol(rootactive[m],L,R+1);
int y = pstmn.sol(rootmin[m],L,R+1);
if(x < y){
res = max(res, x);
l= m+1;
}else{
res = max(res, y);
r = m-1;
}
}
cout << res << endl;
}
}
/*
7 1
3 2 3 1 1 4 7
1 7
*/
/*
atleast x elements should be >= x in the range
x = number of active elements in the range
y = minimum active element in the range
if y == x it doesn't matter you've achieved max possible
4 5 6 7 8
x = 5
y = 4
if y > x then you can achieve x and you want to go to some later versoin of pst (with more elements)
if y < x then you can achieve y and you go to some earlier versin of pst (with less active elements)
*/
