#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,q;
int a[N];
vector<int>P[N];
struct qr
{
    int x,y,v,type;
}node[N*20],tmp[N*20];
int ans[N];
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=l+r>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int p=l,q=mid+1;
    int mx=0,t=0;
    while(p<=mid&&q<=r)
    {
        if(node[p].x>=node[q].x)
        {
            if(node[p].type==0)mx=max(mx,node[p].v);
            tmp[++t]=node[p];
            p++;
        }
        else if(node[p].x<node[q].x)
        {
            if(node[q].type==1)ans[node[q].v]=max(ans[node[q].v],mx);
            tmp[++t]=node[q];
            q++;
        }
    }
    while(p<=mid)
    {
        if(node[p].type==0)mx=max(mx,node[p].v);
        tmp[++t]=node[p];
        p++;
    }
    while(q<=r)
    {
        if(node[q].type==1)ans[node[q].v]=max(ans[node[q].v],mx);
        tmp[++t]=node[q];
        q++;
    }
    for(int i=l;i<=r;i++)node[i]=tmp[i-l+1];   
}
int m;
int query(const vector<int>&v,int p)
{
    int l=0,r=v.size()-1,ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(v[mid]>=p)ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int lim=sqrt(a[i]);
        for(int j=1;j<=lim;j++)
        {
            if(a[i]%j==0)
            {
                P[j].push_back(i);
                if(j*j!=a[i])P[a[i]/j].push_back(i);
            }
        }
    }
    for(int i=1;i<=1000000;i++)
    {
        int lim=P[i].size();
        for(int j=0;j<lim-1;j++)
        {
            int t=P[i][j+1]*2-P[i][j];
            int r=query(P[i],t);
            if(r!=-1)
            {
                //cout<<P[i][j]<<' '<<P[i][j+1]<<' '<<i<<' '<<P[i][r]<<'\n';
                node[++m]={P[i][j],P[i][r],i,0};
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        node[++m]={l,r,i,1};
    }
    sort(node+1,node+m+1,[](const qr&a,const qr&b){return a.y==b.y?(a.x==b.x?a.type<b.type:a.x>b.x):a.y<b.y;});
    cdq(1,m);
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}