#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);
	std::vector<int> cntd(m+1);
	for(int i=1;i<=m;i++)
	{
		for(int j=i;j<=m;j++)
		{
			cntd[j]++;
		}
	}
	for(int x=1;x<=m;x++)
	{
		d[x].reserve(cntd[x]);
	}
	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].reserve(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(ans[i],mx[j]);
		}
	}
	for(int i=0;i<q;i++)
	{
		std::cout<<ans[i]<<"\n";
	}
	return 0;
}