#include <bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0; char ch; bool f=0;
    while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
    if(ch=='-') f=1;
    else x=ch^48;
    while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
    return f?-x:x;
}
const int N=1e6+5;
int n,a[N],q;
vector<int> v[N];
int p[N];
vector<pair<int,int> > V[N];
struct tree{
	int mx;
}t[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
void up(int p){
	t[p].mx=max(t[ls].mx,t[rs].mx);
}
void cg(int p,int w,int l,int r,int d){
	if(l==r){
		t[p].mx=max(t[p].mx,d); return;
	}
	int mid=(l+r)/2;
	if(w<=mid) cg(ls,w,l,mid,d);
	else cg(rs,w,mid+1,r,d);
	up(p);
}
int ask(int p,int st,int en,int l,int r){
	if(st<=l&&r<=en) return t[p].mx;
	int mid=(l+r)/2,v=0;
	if(st<=mid) v=ask(ls,st,en,l,mid);
	if(mid<en) v=max(v,ask(rs,st,en,mid+1,r));
	return v;
}
int ans[N];
int main(){
//	freopen("t2.in","r",stdin);
//	freopen("t2.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read(),v[a[i]].push_back(i);
	for(int d=1;d<=1e6;d++){
		int c=0;
		for(int i=d;i<=1e6;i+=d){
			for(int ps:v[i]) p[++c]=ps;
		}
		sort(p+1,p+1+c);
		for(int i=1;i<c-1;i++){
			int x=p[i],y=p[i+1];
			int l=i+2,r=c;
			while(l<=r){
				int mid=(l+r)/2;
				if(p[mid]-y>=y-x) r=mid-1;
				else l=mid+1;
			}
			if(l<=c) V[p[l]].push_back({x,d});
		}
	}
	for(int i=1;i<=q;i++){
		int l=read(),r=read();
		V[r].push_back({l,-i});
	}
	for(int i=1;i<=n;i++){
		for(auto [x,d]:V[i]){
			if(d>0) cg(1,x,1,n,d);
			else ans[-d]=ask(1,x,i,1,n);
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}