#include <bits/stdc++.h>
using namespace std;
int const N = 50000, M = 100000;
int x[N + 1], n, fr[M + 1];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void flfr() {
  map<int, int> mp, tmp;
  for (int i = 1; i < (int)(n + 1); ++i) {
    swap(mp, tmp);
    mp.clear();
    for (auto it = tmp.begin(); it != tmp.end(); ++it)
      mp[gcd(x[i], it->first)] = it->second;
    int lst = 0;
    mp[x[i]] = i;
    for (auto it = mp.begin(); it != mp.end(); ++it)
      fr[it->first] += it->second - lst, lst = it->second;
  }
  for (int i = 2; i < (int)(M + 1); ++i) fr[i] += fr[i - 1];
}
long long l, r, an;
int j, cr;
inline long long A(long long l, long long r) {
  return l * (r - l + 1) + (r - l) * (r - l + 1) / 2;
}
inline void move(int n, int d, int &i, long long xa, long long xb,
                 long long ana, long long anb, int fra, int frb, int ds) {
  int need = (n - i + d - 1) / d;
  if (ds == -1) ds = need;
  ds = min((long long)ds, min((fr[cr] - r) / fra, (fr[j] + 1 - l) / xa));
  if (ds == need && fr[j] + 1 - l < (ds - 1) * xa + xb) --ds;
  if (ds == need && fr[cr] - r < (ds - 1) * fra + frb) --ds;
  i += d * ds;
  if (i >= n) --ds;
  an -= (l * fra + ana) * ds + (long long)ds * (ds - 1) / 2 * xa * fra;
  l += ds * xa;
  r += (long long)ds * fra;
  if (i >= n) {
    i -= n;
    an -= l * frb + anb;
    l += xb;
    r += frb;
  }
  assert(i >= 0);
}
void go(int n, int d, int &i, long long xa, long long xb, long long ana,
        long long anb, int fra, int frb) {
  if (d == 0) {
    long long ds = min((fr[cr] - r) / fra, (fr[j] + 1 - l) / xa);
    an -= (long long)l * ds * fra + ana * ds +
          (long long)ds * (ds - 1) / 2 * xa * fra;
    r += fra * ds;
    l += xa * ds;
    return;
  }
  if (i >= d) move(n, d, i, xa, xb, ana, anb, fra, frb, -1);
  if (i < d) {
    int nd = d - n % d;
    if (nd == d) nd = 0;
    int cy = (n - 1) / d + 1;
    int nfra = (cy - 1) * fra + frb, nfrb = max(0, cy - 2) * fra + frb;
    long long nxa = (cy - 1) * xa + xb, nxb = max(0, cy - 2) * xa + xb;
    long long nana = (cy - 1) * ana + (cy - 2ll) * (cy - 1) / 2 * xa * fra +
                     (cy - 1) * xa * frb + anb;
    long long nanb = max(0, cy - 2) * ana +
                     max(0ll, (cy - 3ll) * (cy - 2) / 2) * xa * fra +
                     max(0, cy - 2) * xa * frb + anb;
    go(d, nd, i, nxa, nxb, nana, nanb, nfra, nfrb);
  }
  move(n, d, i, xa, xb, ana, anb, fra, frb, -1);
}
long long calc(long long m) {
  long long cs = 0;
  l = 1;
  an = A(2, ((long long)n * (n + 1) >> 1) + 1);
  r = 0;
  j = 1;
  while (fr[j] == 0) ++j;
  for (int i = 1; i < (int)(M + 1); ++i)
    if (r != fr[i]) {
      cr = i;
      long long need = min((m - cs) / i, fr[i] - r);
      an -= need * l;
      r += need;
      cs += need * i;
      if (l > r) {
        an -= A(l + 1, ((long long)n * (n + 1) >> 1) + 1);
        break;
      }
      while (r != fr[i]) {
        long long need = min((m - cs) / i, fr[i] - r);
        an -= need * l;
        r += need;
        cs += need * i;
        if (r == fr[i]) break;
        int t = cs - (m - j + 1);
        if (t < 0) {
          while (l == fr[j] + 1) ++j;
          cs += i;
          ++r;
          while (cs > m) {
            int need = min((cs - m + j - 1) / j, fr[j] + 1 - l);
            l += need;
            cs -= need * j;
            while (l == fr[j] + 1) ++j;
          }
          an -= l;
          t = cs - (m - j + 1);
        }
        if (l > r) {
          an -= A(l + 1, ((long long)n * (n + 1) >> 1) + 1);
          return an;
        }
        go(j, i % j, t, i / j, i / j + 1, i / j, i / j + 1, 1, 1);
        cs = m + t - j + 1;
        if (l == fr[j] + 1)
          while (l == fr[j] + 1) ++j;
        else if (r != fr[i]) {
          long long need = fr[j] + 1 - l;
          cs -= need * j;
          l += need;
          while (l == fr[j] + 1) ++j;
        }
      }
    }
  return an;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < (int)(n + 1); ++i) scanf("%d", x + i);
  flfr();
  long long all = (long long)n * (n + 1) >> 1;
  all = all * (all + 1) >> 1;
  all = all + 1 >> 1;
  long long l = 1, r = (long long)N * N * M;
  while (r > l) {
    long long m = l + r >> 1;
    if (calc(m) < all)
      l = m + 1;
    else
      r = m;
  }
  printf("%lld\n", l);
}
