#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> d(n);


    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }

    int S = 333;
    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;
    };

    auto handle = [&](int x, int y) {
        while (lp[x] < int(stk[x].size()) && y >= stk[x][lp[x]][0]) {
            lp[x]++;
        }
        if (lp[x] >= 1) {
            add(stk[x][lp[x] - 1][1], 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 < q; ++i) {
        auto [l, r, id] = b[i];

        while (p <= r) {
            int x = d[p];
            for (int j = 1; j * j <= x; ++j) {
                if (x % j == 0) {
                    handle(j, p);
                    if (j * j != x) {
                        handle(x / j, p);
                    }
                }
            }
            p++;
        }
        ans[id] = query(l, r);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}