#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void Out(int x) {
  if (x > 9) Out(x / 10);
  putchar('0' + x % 10);
}
int gcd(int x, int y) {
  if (!y) return x;
  return gcd(y, x % y);
}
long long qpow(long long x, long long y, long long P) {
  long long re = 1;
  while (y) {
    if (y & 1) re = re * x % P;
    x = x * x % P;
    y >>= 1;
  }
  return re;
}
long long likegcd(long long a, long long b, long long c, long long n) {
  long long re, p;
  if (c < 0) return likegcd(-a, -b, -c, n);
  if (a < 0 || b < 0) {
    re = likegcd(a % c + c, b % c + c, c, n);
    re += n * (n + 1) / 2 * ((a / c) - 1);
    re += (n + 1) * ((b / c) - 1);
    return re;
  }
  if (a == 0) {
    re = (b / c) * (n + 1);
    return re;
  }
  if (a >= c || b >= c) {
    p = likegcd(a % c, b % c, c, n);
    re = n * (n + 1) / (long long)2 * (a / c);
    re += (b / c) * (n + 1);
    re += p;
    return re;
  }
  long long m = (a * n + b) / c;
  p = likegcd(c, c - b - 1, a, m - 1);
  re = -p + n * m;
  return re;
}
const long double eps = 1e-6;
const int N = 5e4 + 10;
const int mx = 1e5 + 1;
int n, x;
int tp = 0;
pair<int, int> q[50];
long long a[100050];
long long num[100050], sum[100050];
long long check(long long M) {
  long long re = 0, t;
  int i = 1, j;
  long long A, B, V, x;
  if (a[1]) {
    t = min(M, a[1]);
    re += (long long)a[1] * t - (long long)t * (t - 1) / 2;
  }
  for (long long r = 2; r <= mx; ++r) {
    if (!a[r]) continue;
    t = min(M / r, a[r]);
    re += (long long)a[r] * t - (long long)t * (t - 1) / 2;
    if (sum[r] - sum[i - 1] <= M) {
      re += (long long)(num[r - 1] - num[i - 1]) * (long long)a[r];
      continue;
    }
    while (sum[r - 1] - sum[i] >= M) ++i;
    j = i;
    while (sum[r] - sum[j] >= M && j + 1 != r) ++j;
    if (r - 1 >= j + 1)
      re += (long long)(num[r - 1] - num[j]) * (long long)a[r];
    for (long long k = i; k <= j; ++k) {
      if (!a[k]) continue;
      A = r;
      B = k;
      V = 0;
      if (r - 1 >= k + 1) V = sum[r - 1] - sum[k];
      V = M - V;
      if (V <= 0) continue;
      t = min(a[r], (V - B) / A);
      if (t <= 0) continue;
      x = likegcd(-A, V, B, t);
      x = x - (V / B);
      re += x;
      t = min(a[r], (V - (long long)a[k] * B) / A);
      if (t <= 0) continue;
      x = likegcd(-A, V, B, t);
      x = x - (V / B);
      re -= x;
      re += (long long)a[k] * t;
    }
    i = j;
  }
  return re;
}
int main() {
  pair<int, int> aaa;
  int x;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    q[++tp] = pair<int, int>(x, i);
    for (int j = tp - 1; j >= 1; --j) q[j].first = gcd(q[j].first, x);
    int tmp = 1;
    for (int j = 2; j <= tp; ++j)
      if (q[j].first != q[j - 1].first) q[++tmp] = q[j];
    tp = tmp;
    for (int j = 1; j <= tp; ++j)
      a[q[j].first] += (j == tp ? i + 1 : q[j + 1].second) - q[j].second;
  }
  for (int i = 1; i <= mx; ++i) {
    num[i] = num[i - 1] + a[i];
    sum[i] = sum[i - 1] + (long long)a[i] * i;
  }
  long long P = (long long)n * (n + 1) / 2;
  P = P * (P + 1) / 2;
  P = (P + 1) / 2;
  long long l = 1, r = sum[mx], mid;
  while (l != r) {
    mid = l + r >> 1;
    if (check(mid) >= P)
      r = mid;
    else
      l = mid + 1;
  }
  cout << l << endl;
}
