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



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    constexpr int N = 1e6 + 1;
    vector<vector<array<int, 2>>> stk(N);
    vector<int> lp(N, 0);
    vector<int> pre(N, -1);
    vector<int> lst(N, -1);
    vector<array<int, 3>> a;

    auto handle = [&](int x, int y) {
        while (lp[x] < stk[x].size() && y >= stk[x][lp[x]][0]) {
            lp[x]++;
        }
        if (lp[x] >= 1 && lst[x] != stk[x][lp[x] - 1][1]) {
            a.push_back({stk[x][lp[x] - 1][1], y, x});
            lst[x] = stk[x][lp[x] - 1][1];
        }
        // if (lp[x] >= 1) {
        //     a.push_back({stk[x][lp[x] - 1][1], y, x});
        // }
        
        if (pre[x] != -1) {
            int now = 2 * y - pre[x]; 
            if (stk[x].size() && now <= stk[x].back()[0]) {
                stk[x].pop_back();
            }
            stk[x].push_back({now, pre[x]});
            lp[x] = min(lp[x], int(stk[x].size()));
        }
        pre[x] = y;
    };

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        for (int j = 1; j * j <= x; ++j) {
            if (x % j == 0) {
                handle(j, i);
                if (j * j != x) {
                    handle(x / j, i);
                }
            }
        }
    }

    int S = sqrt(n);
    if (S <= 0) {
        S = 1;
    }
    int cnt = (n + S - 1) / S;
    vector<int> L(cnt), R(cnt);
    vector<int> blk(cnt), c(n);
    for (int i = 0; i < cnt; ++i) {
        L[i] = i * S;
        R[i] = min((i + 1) * S - 1, n - 1);
    }

    vector<array<int, 3>> b(q);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        b[i] = {l, r, i};
    }
    vector<int> ans(q);

    sort(b.begin(), b.end(), [&](const auto &a, const auto &b) {
        return a[1] < b[1];
    });

    int p = 0;

    #define belong(x) ((x) / S)

    auto add = [&](int x, int y) {
        c[x] = max(c[x], y);
        blk[belong(x)] = max(blk[belong(x)], y);
    };

    auto query = [&](int l, int r) {
        int ll = belong(l), rr = belong(r);

        if (ll == rr) {
            int ans = 0;
            for (int i = l; i <= r; ++i) {
                ans = max(ans, c[i]);
            }
            return ans;
        }

        int ans = 0;
        for (int i = l; i <= R[ll]; ++i) {
            ans = max(ans, c[i]);
        }
        for (int i = L[rr]; i <= r; ++i) {
            ans = max(ans, c[i]);
        }

        for (int i = ll + 1; i <= rr - 1; ++i) {
            ans = max(ans, blk[i]);
        }
        return ans;
    };

    for (int i = 0; i < q; ++i) {
        auto [l, r, id] = b[i];

        while (p < int(a.size()) && a[p][1] <= r) {
            add(a[p][0], a[p][2]);
            p++;
        }
        ans[id] = query(l, r);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}