#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MAXM=1e6+10;
int n,q,ans[MAXN],a[MAXN];
vector<int> occ[MAXM];
int tr[MAXN];
vector<pair<int,int>> upd[MAXN],qr[MAXN];
void update(int pos,int v) {
	while(pos<=n) tr[pos]=max(tr[pos],v),pos+=pos&-pos;
	return ;	
}
int query(int pos) {
	int ans=1;
	while(pos) ans=max(ans,tr[pos]),pos-=pos&-pos;
	return ans;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,n) {
		cin>>a[i];
		ffor(j,1,a[i]/j) if(a[i]%j==0) {
			occ[j].push_back(i);
			if(a[i]/j!=j) occ[a[i]/j].push_back(i);
		}
	}
	ffor(i,1,q) {int l,r;cin>>l>>r,qr[l].push_back({r,i});}
	ffor(i,2,1000000) if(occ[i].size()>=3) {
		ffor(j,0,occ[i].size()-3) {
			int id1=occ[i][j],id2=occ[i][j+1],id3=2*id2-id1;
			int pos=lower_bound(occ[i].begin(),occ[i].end(),id3)-occ[i].begin();
			if(pos>=occ[i].size()) continue ;
			upd[id1].push_back({occ[i][pos],i});
		}
	}
	roff(i,n,1) {
		for(auto pr:upd[i]) update(pr.first,pr.second);
		for(auto pr:qr[i]) ans[pr.second]=query(pr.first);	
	}
	ffor(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}