#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
char buf[1<<21], *p1, *p2;
#define GC p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++
inline int read() {
	int x = 0; char ch = GC;
	while(ch > '9' || ch < '0') ch = GC;
	while(ch >= '0' && ch <= '9') x = (x<<1) + (x<<3) + (ch^48), ch = GC;
	return 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;
}