#include<bits/stdc++.h>
using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
constexpr int B=400;
template <typename T>
struct Fenwick
{
int n;
std::vector<T> a;
Fenwick(int n_=0)
{
init(n_);
}
void init(int n_)
{
n=n_;
a.assign(n,T{});
}
void add(int x,const T& v)
{
for(int i=x+1;i<=n;i+=i&-i)
{
a[i-1]=a[i-1]+v;
}
}
T sum(int x)
{
T ans{};
for(int i=x;i>0;i-=i&-i)
{
ans=ans+a[i-1];
}
return ans;
}
T rangeSum(int l,int r)
{
return sum(r)-sum(l);
}
int select(const T& k)
{
int x=0;
T cur{};
for(int i=1<<std::__lg(n);i;i/=2)
{
if(x+i<=n&&cur+a[x+i-1]<=k)
{
x+=i;
cur=cur+a[x-1];
}
}
return x;
}
};
struct Max
{
int x=0;
};
Max operator+(const Max& a,const Max& b)
{
return {std::max(a.x,b.x)};
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,q;
std::cin>>n>>q;
std::vector<int> a(n);
for(int i=0;i<=n;i++)
{
std::cin>>a[i];
}
const int m=*std::max_element(a.begin(),a.end());
std::vector<std::vector<int>> d(m+1);
for(int i=1;i<=m;i++)
{
for(int j=i;j<=m;j++)
{
d[j].push_back(i);
}
}
std::vector<std::vector<int>> f(m+1);
std::vector<int> cnt(m+1);
for(int i=0;i<n;i++)
{
for(auto x:d[a[i]])
{
cnt[x]++;
}
}
for(int x=1;x<=m;x++)
{
f[x].reverse(cnt[x]);
}
for(int i=0;i<n;i++)
{
for(auto x:d[a[i]])
{
f[x].push_back(i);
}
}
std::vector<std::vector<std::array<int,2>>>e(n);
for(int x=1;x<=m;x++)
{
for(int i=1;i+1<f[x].size();i++)
{
auto it=std::lower_bound(f[x].begin(),f[x].end(),f[x][i]*2-f[x][i-1]);
if(it!=f[x].end())
{
e[f[x][i-1]].push_back({*it,x});
}
}
}
//std::sort(e.begin(),e.end(),std::greater());
std::vector<std::array<int,3>> ask(q);
for(int i=0;i<q;i++)
{
int l,r;
std::cin>>l>>r;
l--;
ask[i]={l,r,i};
}
std::sort(ask.begin(),ask.end(),std::greater());
//Fenwick<Max> fen(n);
std::vector<int> ans(q);
std::vector<int> mx(n);
std::vector<int> blk(n/B+1);
for(int j=n;auto [l,r,i]:ask)
{
while(j>l)
{
j--;
for(auto [x,y]:e[j])
{
mx[x]=std::max(mx[x],y);
int bx=x/B;
blk[bx]=std::max(blk[bx],y);
}
}
int br=(r-1)/B;
for(int j=0;j<br;j++)
{
ans[i]=std::max(ans[i],blk[j]);
}
for(int j=br*B;j<r;j++)
{
ans[i]=std::max(anx[i],mx[j]);
}
}
for(int i=0;i<q;i++)
{
std::cout<<ans[i]<<"\n";
}
return 0;
}