#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second

constexpr int N = 1e6+5;

int n,m;
int a[N];
vector<int> ys[N];
vector<int> pos[N];
vector<pair<int,int>> Q[N];
int ans[N];

vector<pair<int,int>> e[N];

int c[N];
void upd(int x,int k){while(x<=n)c[x]=max(c[x],k),x+=x&-x;}
int qry(int x){int ret=0;while(x)ret=max(ret,c[x]),x^=x&-x;return ret;}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    rep(i,1,n)cin>>a[i];
    rep(i,1,1e6)for(int j=i;j<=1e6;j+=i)ys[j].push_back(i);
    rep(i,1,n)for(auto j:ys[a[i]])pos[j].push_back(i);
    rep(i,1,1e6)if(pos[i].size()>=3){
        for(int j=0;j<pos[i].size()-2;++j){
            int p=lower_bound(allc(pos[i]),2*pos[i][j+1]-pos[i][j])-pos[i].begin();
            if(p<pos[i].size())e[pos[i][j]].emplace_back(i,pos[i][p]);
        }
    }
    rep(i,1,m){
        int l,r;cin>>l>>r;
        Q[l].emplace_back(r,i);
    }
    per(i,n,1){
        for(auto p:e[i])upd(p.sec,p.fir);
        for(auto p:Q[i])ans[p.sec]=qry(p.fir);
    }
    rep(i,1,m)cout<<ans[i]<<'\n';
}