#include <bits/stdc++.h>
#define open freopen("1.in","r",stdin),freopen("1.out","w",stdout)
using namespace std;const unsigned N=1e5+1,inf=1e9+7;
#define ge getchar/*_unlocked*/()
#define pu(c) putchar/*_unlocked*/(c)
#define cr register unsigned char
#define dig(c) (c<0b111011&&c>0b101111)
#define int register unsigned
inline unsigned rd(){cr c=ge;while(!dig(c))c=ge;int s=0;while(dig(c))s=(s<<0b11)+(s<<0b1)+(c^0b110000),c=ge;return s;}inline void wt(int x){if(!x)return (void)(pu(0b110000));static unsigned char c[0b1011],s;s=0b0;while(x)c[++s]=x%0b1010,x/=0b1010;while(s)pu(c[s--]^0b110000);}
#define void inline void
unsigned a[N],id[N],ans[N],l,r,_;mt19937 R(time(0));const unsigned n=rd(),q=rd();const unsigned S=12;
class Fhq_Treap{private:unsigned t[N],k[N],l[N],r[N],s[N],id,rt;
	inline unsigned ne(int v){t[++id]=v,k[id]=R(),l[id]=r[id]=0,s[id]=1;return id;}
	#define up(o) s[o]=s[l[o]]+s[r[o]]+1
	void sp(int p,int v,int &x,int &y){if(!p){x=y=0;return;}
		if(t[p]<=v){x=p;sp(r[x],v,r[x],y);up(x);}
		else       {y=p;sp(l[y],v,x,l[y]);up(y);}}
	inline unsigned me(int x,int y){if(!x||!y)return x|y;
		if(k[x]<k[y]){r[x]=me(r[x],y);return up(x),x;}
		else         {l[y]=me(x,l[y]);return up(y),y;}}
	inline unsigned gt(int o,int x){int c=s[l[o]];return x<=c?gt(l[o],x):x==c+1?t[o]:gt(r[o],x-c-1);}
	public:void clear(){id=rt=l[0]=r[0]=s[0]=t[0]=0;};
	void ins(int v){int x,y,z=ne(v);sp(rt,v,x,y);rt=me(me(x,z),y);}
	void del(int v){int x,y,z;sp(rt,v,x,z);sp(x,v-1,x,y);y=me(l[y],r[y]);rt=me(me(x,y),z);}
	inline unsigned pre(int v){int x,y,res;sp(rt,v-1,x,y);if(!x)return -inf;res=gt(x,s[x]);rt=me(x,y);return res;}
	inline unsigned nxt(int v){int x,y,res;sp(rt,v  ,x,y);if(!y)return  inf;res=gt(y,   1);rt=me(x,y);return res;}}t;
void init(){for(int i=0,j;i*S<=n;++i)for(j=S*i+1;j<=S*(i+1);++j)id[j]=i;for(int i=n;!id[i];--i)id[i]=S+1;}
struct query{unsigned l,r,x;inline bool operator<(const query&b){return r+b.l<b.r+l;}}tmp;vector<query>Q[N];
void MIN(int v){_>v?_=v:0;}
void add(int v){t.ins(v);MIN(v-t.pre(v));MIN(t.nxt(v)-v);}
void sub(int v){t.del(v);}
void solve(vector<query>b){if(!b.size())return;l=b[0].l,r=b[0].r;_=inf;
	for(int i=l;i<=r;++i)add(a[i]);ans[b[0].x]=_;for(int i=1;i<b.size();++i){_=inf;
		while(l<b[i].l)sub(a[l++]);while(r>b[i].r)sub(a[r--]),r;
		while(l>b[i].l)add(a[--l]);while(r<b[i].r)add(a[++r]),r;
		ans[b[i].x]=_;_=inf;}t.clear();}
signed main(){init();for(int i=1;i<=n;++i)a[i]=rd();for(int i=1;i<=q;++i){tmp=query{rd(),rd(),i};
	Q[id[tmp.l]].emplace_back(tmp);}for(int i=0;i<S+2;++i){sort(Q[i].begin(),Q[i].end());solve(Q[i]);}
	for(int i=1;i<=q;++i)wt(ans[i]),pu(0b1010);}