#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "URDL";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
pair<int, int> q[100005];
int a[100005];
long long A[100005], S[100005];
long long work(long long l, long long r, long long d) {
  if (r <= d) return (r + l) * (r - l + 1) / 2;
  if (l >= d) return (r - l + 1) * d;
  return d * (r - d) + (l + d) * (d - l + 1) / 2;
}
long long F(long long a, long long b, long long c, long long n) {
  if (a == 0) 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);
  return (a * n + b) / c * n - F(c, c - b - 1, a, (a * n + b) / c - 1);
}
long long f(long long a, long long b, long long c, long long n) {
  if (c < 0) {
    a = -a;
    b = -b;
    c = -c;
  }
  if (a <= 0) {
    b += a * n;
    a = -a;
  }
  if (b < 0) {
    long long x = (a - b - 1) / a;
    if (x >= 0) {
      n -= x;
      b += x * a;
    }
  }
  if (n < 0) return 0;
  return F(a, b, c, n);
}
long long ck(long long mid) {
  long long ans = 0;
  int j = 1;
  for (int(i) = 1; (i) <= (int)(100005 - 1); (i)++)
    if (a[i]) {
      if (S[i] <= mid)
        ans += A[i - 1] * a[i] + (long long)a[i] * (a[i] + 1) / 2;
      else {
        long long s = 1;
        while (j < i && s <= a[i]) {
          if (S[i - 1] - S[j] + (long long)s * i > mid)
            j++;
          else {
            long long s1 =
                min((mid - (S[i - 1] - S[j])) / i, (long long)a[i]) + 1;
            ans += f(-i, mid - (S[i - 1] - S[j]) - s * i, j, s1 - 1 - s);
            ans -= f(-i, mid - (S[i - 1] - S[j]) - s * i - (long long)a[j] * j,
                     j, s1 - 1 - s);
            ans += (s + s1 - 1) * (s1 - s) / 2;
            ans += (s1 - 1 - s + 1) * (A[i - 1] - A[j]);
            s = s1;
            if (s <= a[i]) j++;
          }
        }
        if (j == i) ans += work(s, a[i], mid / i);
      }
    }
  return ans;
}
void fmain(int tid) {
  scanf("%d", &n);
  int tp = 0;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    int x;
    scanf("%d", &x);
    q[++tp] = {x, i};
    for (int j = tp; j; j--) q[j].first = gcd1(q[j].first, x);
    int tmp = 1;
    for (int j = 2; j <= tp; j++)
      if (q[j].first != q[tmp].first) {
        q[++tmp] = q[j];
      }
    tp = tmp;
    for (int(j) = 1; (j) <= (int)(tp); (j)++) {
      int ed = j == tp ? i + 1 : q[j + 1].second;
      a[q[j].first] += ed - q[j].second;
    }
  }
  for (int(i) = 1; (i) <= (int)(100005 - 1); (i)++) {
    A[i] = A[i - 1] + a[i];
    S[i] = S[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 = 0, r = S[100005 - 1];
  while (l + 1 < r) {
    long long mid = (l + r) / 2;
    if (ck(mid) < p)
      l = mid;
    else
      r = mid;
  }
  printf("%lld\n", r);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
