#include <bits/stdc++.h>
using namespace std;
long long n, m, num[100100], cnt[100100], qzc[100100], qzs[100100];
namespace Get {
long long g[100100][20];
inline long long gcd(long long u, long long v) {
  for (; u && v && u != v;) {
    swap(u, v);
    u %= v;
  }
  return max(u, v);
}
void work() {
  long long i, j, k, t, l;
  for (i = 1; i <= n; i++) g[i][0] = num[i];
  for (i = 1; i <= 16; i++) {
    for (j = 1; j + (1 << (i - 1)) <= n; j++) {
      g[j][i] = gcd(g[j][i - 1], g[j + (1 << (i - 1))][i - 1]);
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = l = i, t = num[i]; j <= n;) {
      t = gcd(t, num[j]);
      for (k = 16; k >= 0; k--) {
        if ((j + (1 << k)) > n + 1) continue;
        if (g[j][k] % t == 0) {
          j += (1 << k);
        }
      }
      cnt[t] += j - l;
      l = j;
    }
  }
}
}  // namespace Get
long long f(long long a, long long b, long long c, long long n) {
  if (n < 0) return 0;
  if (!a) return b / c * (n + 1);
  if (a >= c || b >= c)
    return f(a % c, b % c, c, n) + a / c * n * (n + 1) / 2 + b / c * (n + 1);
  long long m = (a * n + b) / c;
  return m * n - f(c, c - b - 1, a, m - 1);
}
inline long long ask(long long a, long long b, long long c) {
  if (c < 0) return 0;
  return c / a + 1 + f(a, c % a, b, c / a);
}
inline long long solve(long long a, long long ca, long long b, long long cb,
                       long long c) {
  if (a * (ca - 1) + b * (cb - 1) <= c) return ca * cb;
  if (c < 0) return 0;
  return ask(a, b, c) - ask(a, b, c - a * ca) - ask(a, b, c - b * cb) +
         ask(a, b, c - a * ca - b * cb);
}
inline long long calc(long long u) {
  long long i, j, l, r, t, res = 0;
  for (i = 1; i <= 100000; i++) {
    if (!cnt[i]) continue;
    t = min(cnt[i], u / i);
    res += cnt[i] * t - t * (t - 1) / 2;
  }
  for (l = r = 1; l < 100000; l++) {
    if (!cnt[l]) continue;
    if (l < r) res += cnt[l] * (qzc[r - 1] - qzc[l]);
    for (; r <= 100000 && qzs[r] - qzs[l] <= u; r++) {
      if (l != r && cnt[r]) {
        res += solve(l, cnt[l], r, cnt[r], u - (qzs[r - 1] - qzs[l]) - l - r);
      }
    }
    if (r <= 100000) {
      if (l != r && cnt[r]) {
        res += solve(l, cnt[l], r, cnt[r], u - (qzs[r - 1] - qzs[l]) - l - r);
      }
    }
  }
  return res;
}
int main() {
  long long i, j, l, r, mid;
  cin >> n;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &num[i]);
  }
  Get::work();
  m = (n + 1) * n / 2;
  m = (m + 1) * m / 2;
  m = (m + 1) / 2;
  for (i = 1; i <= 100000; i++) {
    qzc[i] = qzc[i - 1] + cnt[i];
    qzs[i] = qzs[i - 1] + cnt[i] * i;
  }
  for (l = 1, r = qzs[100000] + 1; l < r;) {
    mid = ((l + r) >> 1);
    if (calc(mid) < m)
      l = mid + 1;
    else
      r = mid;
  }
  cout << l;
}
