#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int maxn(1 << 21 | 1);
char *iS, *iT, ibuf[maxn], obuf[maxn], *oS = obuf, *oT = obuf + maxn - 1, c,
                                       st[20];
int f, tp, len;
inline char getc() {
  return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin),
                     iS == iT ? EOF : *iS++)
                  : *iS++;
}
template <class T>
inline void read(T &x) {
  for (c = getc(), f = 1; c < '0' || c > '9'; c = getc()) f = c == '-' ? -1 : 1;
  for (x = 0; c >= '0' && c <= '9'; c = getc()) x = x * 10 + (c ^ 48);
  x *= f;
}
template <class T, class... Other>
inline void read(T &x, Other &...y) {
  read(x), read(y...);
}
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void putc(char ch) {
  *oS++ = ch;
  if (oS == oT) flush();
}
template <class T>
inline void print(T x, char ch = '\n') {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putc(st[tp--]);
  putc(ch);
}
template <class T, class... Other>
inline void print(T x, Other... y) {
  print(x), print(y...);
}
inline void print_str(char *s) {
  for (len = strlen(s), f = 0; f < len; ++f) putc(s[f]);
}
inline void read_str(char *s, int &l) {
  for (l = 0, c = getc(); (c < 'a' || c > 'z') && (c < 'A' || c > 'Z');
       c = getc())
    ;
  for (; (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); c = getc())
    s[l++] = c;
  s[l] = '\0';
}
}  // namespace IO
using IO ::flush;
using IO ::print;
using IO ::print_str;
using IO ::read;
using IO ::read_str;
template <class T>
inline void cmax(T &x, T y) {
  x = x >= y ? x : y;
}
template <class T, class... Other>
inline void cmax(T &x, T y, Other... z) {
  Cmax(x, y), Cmax(x, z...);
}
template <class T>
inline void cmin(T &x, T y) {
  x = x <= y ? x : y;
}
template <class T, class... Other>
inline void cmin(T &x, T y, Other... z) {
  Cmin(x, y), Cmin(x, z...);
}
inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
const int mod(998244353);
inline void inc(int &x, const int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void dec(int &x, const int y) { x = x - y < 0 ? x - y + mod : x - y; }
inline int add(const int x, const int y) {
  return x + y >= mod ? x + y - mod : x + y;
}
inline int sub(const int x, const int y) {
  return x - y < 0 ? x - y + mod : x - y;
}
inline int fpow(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % mod)
    if (y & 1) ret = ret * x % mod;
  return ret;
}
const int maxn(1e5 + 5);
int n, seq[maxn], st[18][maxn], lg[maxn], mx;
long long cnt[maxn], sum[maxn], sumv[maxn];
inline int query_gcd(int l, int r) {
  int len = lg[r - l + 1];
  return gcd(st[len][l], st[len][r - (1 << len) + 1]);
}
inline long long calc(long long m, long long a, long long b, long long c) {
  if (c < 0) c = -c, a = -a, b = -b;
  if (m <= 0) return 0;
  if (m == 1) return (a + b) / c;
  if (!a) return b / c * m;
  long long ma, mb, ra, rb, nm;
  if (b < 0 || b >= c || a < 0 || a >= c) {
    ma = (a % c + c) % c, mb = (b % c + c) % c;
    ra = (a - ma) / c, rb = (b - mb) / c;
    return calc(m, ma, mb, c) + (ra * m * (m + 1) >> 1) + rb * m;
  }
  nm = (a * m + b) / c;
  return nm * m - calc(nm, c, -b - 1, a);
}
inline long long solve(long long x, long long cx, long long y, long long cy,
                       long long s) {
  if (!cx || !cy) return 0;
  if (cx * x + cy * y <= s) return cx * cy;
  long long s1 = s - cy * y, s2 = s - cx * x, ss = s - cx * x - cy * y;
  return calc(s / x, -x, s, y) - calc(s1 / x, -x, s1, y) -
         calc(s2 / y, -y, s2, x) + calc(ss / x, -x, ss, y);
}
inline long long check(long long mid) {
  int i, j, p;
  long long ret = 0, s, k;
  for (i = j = 1; i <= mx; ++i) {
    if (!cnt[i]) continue;
    k = min(mid / i, cnt[i]);
    if (k) ret += cnt[i] * k - (k * (k - 1) >> 1);
    while (j < mx && sumv[j + 1] - sumv[i - 1] <= mid) ++j;
    if (j >= i) ret += cnt[i] * (sum[j] - sum[i]);
    if (j == mx) continue;
    for (p = max(i, j); p < mx; ++p) {
      s = mid - sumv[p] + sumv[i];
      if (s < 0) break;
      ret += solve(i, cnt[i], p + 1, cnt[p + 1], s);
    }
  }
  return ret;
}
int main() {
  int i, j, k, p, g;
  long long ql = 1, qr = 0, mid, ans, lim;
  read(n);
  for (i = 1; i <= n; ++i) read(seq[i]), st[0][i] = seq[i], cmax(mx, seq[i]);
  for (i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (j = 1; j <= lg[n]; ++j)
    for (i = 1; i + (1 << j) - 1 <= n; ++i)
      st[j][i] = gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  for (i = 1; i <= n; ++i)
    for (j = i; j <= n; ++j) {
      g = query_gcd(i, j), p = j;
      for (k = lg[n - j]; ~k; --k)
        if (p + (1 << k) - 1 <= n && st[k][p] % g == 0) p += (1 << k) - 1;
      cnt[g] += p - j + 1, j = p;
    }
  for (i = 1; i <= mx; ++i)
    qr += cnt[i] * i, sum[i] = sum[i - 1] + cnt[i],
                      sumv[i] = sumv[i - 1] + cnt[i] * i;
  lim = (long long)n * (n + 1) >> 1, lim = lim * (lim + 1) >> 1,
  lim = (lim + 1) >> 1;
  while (ql <= qr) {
    mid = (ql + qr) >> 1;
    if (check(mid) >= lim)
      qr = mid - 1, ans = mid;
    else
      ql = mid + 1;
  }
  print(ans);
  return flush(), 0;
}
