#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x > y ? y : x;
}
template <typename T>
void add(T &x, T y, T mod) {
  x = x + y > mod ? x + y - mod : x + y;
}
template <typename T>
void sub(T &x, T y, T mod) {
  x = x - y < 0 ? x - y + mod : x - y;
}
template <typename T>
void multi(T &x, T y, T mod) {
  x = 1ll * x * y % mod;
}
const int INF = (1ll << 30);
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const long long N = 1e5 + 7;
long long n, p, tp, a[N], t[N], num[N], cnt[N], cnt_sum[N], num_sum[N];
pair<long long, long long> stk[N];
inline long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  return b == 0 ? a : gcd(b, a % b);
}
inline long long f(long long n, long long a, long long b, long long c) {
  if (n < 0) return 0;
  if (a < 0) return f(n, -a, b + n * a, c);
  if (b < 0) {
    if (!a) return 0;
    long long d = ceil(1.0 * (-b) / a);
    return f(n - d, a, b + a * d, c);
  }
  if (!a) return (b / c) * (n + 1);
  if (a >= c || b >= c)
    return f(n, a % c, b % c, c) + (a / c) * n * (n + 1) / 2 +
           (b / c) * (n + 1);
  long long m = (a * n + b) / c;
  return 1ll * n * m - f(m - 1, c, c - b - 1, a);
}
inline long long calc(long long l, long long r, long long k) {
  if (l == 0 || l >= r) return 0;
  if (num_sum[r] - num_sum[l - 1] <= k) return cnt[l] * cnt[r];
  long long x = num_sum[r - 1] - num_sum[l], sum = 0;
  sum += f(cnt[l], -num[l], k - x, num[r]) - std::max(0ll, (k - x) / num[r]);
  sum -= f(cnt[l], -num[l], k - x - num[r] * cnt[r], num[r]) -
         std::max(0ll, ((k - cnt[r] * num[r] - x) / num[r]));
  return sum;
}
inline bool check(long long x) {
  long long ret = 0;
  for (long long i = 1; i <= p; i++) {
    long long count = min(x / num[i], cnt[i]);
    ret += count * cnt[i] - count * (count - 1) / 2;
  }
  long long r = 1;
  for (long long l = 1; l <= p; l++) {
    if (num[l] > x) break;
    r = max(l + 1, r);
    while (r <= p && num_sum[r] - num_sum[l - 1] <= x) r++;
    ret += (cnt_sum[r - 1] - cnt_sum[l]) * cnt[l];
    while (r <= p && num_sum[r] - num_sum[l] <= x) ret += calc(l, r, x), r++;
    ret += calc(l, r, x);
  }
  long long m = 1ll * (n + 1) * n / 2;
  return 2 * ret >= m * (m + 1) / 2;
}
signed main() {
  read(n);
  for (long long i = 1; i <= n; i++) read(a[i]);
  for (long long i = 1; i <= n; i++) {
    stk[++tp] = make_pair(a[i], i);
    p = 0;
    for (long long j = 1; j <= tp; j++) {
      stk[j].first = gcd(stk[j].first, a[i]);
      if (stk[j].first == stk[p].first) continue;
      stk[++p] = stk[j];
    }
    tp = p;
    for (long long j = 1; j < tp; j++)
      t[stk[j].first] += stk[j + 1].second - stk[j].second;
    t[stk[p].first] += i - stk[p].second + 1;
  }
  p = 0;
  for (long long i = 1; i <= N - 7; i++)
    if (t[i]) num[++p] = i, cnt[p] = t[i];
  for (long long i = 1; i <= p; i++)
    cnt_sum[i] = cnt_sum[i - 1] + cnt[i],
    num_sum[i] = num_sum[i - 1] + num[i] * cnt[i];
  long long l = 0, r = 1e15, ans = -1;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  printf("%lld\n", ans);
  return 0;
}
