#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1.5e5 + 5, V = 1e6, MaxV = 1e6 + 5;
int n, qn, ans[Maxn], a[Maxn];
vector<int> d[MaxV], g[MaxV];
vector<pair<int, int>> p[Maxn], q[Maxn];
int fen[Maxn];
void upd(int x, int y) { for (; x <= n; x += x & -x) fen[x] = max(fen[x], y); }
int ask(int x) { int r = 0; for (; x; x -= x & -x) r = max(r, fen[x]); return r; }
int main(void) {
  ios_base::sync_with_stdio(false);
  cin >> n >> qn;
  for (int i = 1; i <= V; ++i)
    for (int j = i; j <= V; j += i) d[j].push_back(i);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) for (int j: d[a[i]]) g[j].push_back(i);
  for (int d = V; d >= 1; --d) {
    for (int i = 0; i < (int)g[d].size() - 2; ++i) {
      int x = g[d][i], y = g[d][i + 1], z = 2 * y - x;
      int w = lower_bound(g[d].begin(), g[d].end(), z) - g[d].begin();
      if (w != (int)g[d].size()) p[x].push_back({g[d][w], d});
    }
  }
  for (int i = 1; i <= qn; ++i) {
    int l, r; cin >> l >> r;
    q[l].push_back({r, i});
  }
  // x >= L, y <= R;
  for (int i = n; i >= 1; --i) {
    for (auto [y, w]: p[i]) upd(y, w);
    for (auto [y, id]: q[i]) ans[id] = ask(y);
  }
  for (int i = 1; i <= qn; ++i)
    printf("%d\n", ans[i]);
  return 0;
} // main