#include<bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,ubuf[1<<23],*u=ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
	TP x=0;
	int f=0;
	char ch=getchar();
	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
	while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
	(read(args),...);
}
template<typename TP> inline void write(TP x)
{
	(x<0)?(putchar('-'),x=-x):0;
	(x>9)?(write(x/10),0):0;
	putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
	write<TP>(x);
	puts("");
}
int n,q,a[200001],siz,bel[200001],ans[200001];
struct Q
{
	int l,r,id;
} query[200001];
set<int> st,res;
map<int,int> acnt,rcnt;
struct Mo_algo
{
	inline void emplace(int x)
	{
		x=a[x];
		++acnt[x];
		if(st.find(x)==st.end())
		{
			st.emplace(x);
			auto pos=st.find(x);
			int lx=pos==st.begin()?0x7fffffff:x-*prev(pos),rx=pos==prev(st.end())?0x7ffffff:*next(pos)-x;
			++rcnt[lx],++rcnt[rx];
			res.emplace(lx),res.emplace(rx);
			if(lx<1e7&&rx<1e7)
			{
				--rcnt[lx+rx];
				if(!rcnt[lx+rx]) res.erase(lx+rx);
			}
		}
	}
	inline void erase(int x)
	{
		x=a[x];
		--acnt[x];
		if(!acnt[x])
		{
			auto pos=st.find(x);
			int lx=pos==st.begin()?0x7fffffff:x-*prev(pos),rx=pos==prev(st.end())?0x7ffffff:*next(pos)-x;
			--rcnt[lx],--rcnt[rx];
			if(!rcnt[lx]) res.erase(lx);
			if(!rcnt[rx]) res.erase(rx);
			if(lx<1e7&&rx<1e7) res.emplace(lx+rx);
			st.erase(x);
		}
	}
} itv;
signed main()
{
	read(n,q);
	siz=sqrt(n);
	rep(i,1,n) read(a[i]);
	rep(i,1,q) read(query[i].l,query[i].r),query[i].id=i,bel[i]=i/siz+1;
	sort(query+1,query+q+1,[](Q a,Q b){return (bel[a.l]^bel[b.l])?a.l<b.l:((bel[a.l]&1)?a.r<b.r:a.r>b.r);});
	int lef=1,rig=0;
	rep(i,1,q)
	{
		while(rig<query[i].r) itv.emplace(++rig);
		while(lef>query[i].l) itv.emplace(--lef);
		while(lef<query[i].l) itv.erase(lef++);
		while(rig>query[i].r) itv.erase(rig--);
		ans[query[i].id]=*res.begin();
	}
	rep(i,1,q) writeln(ans[i]);
	return 0;
}