#include <bits/stdc++.h>
using namespace std;
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);
}
const int N = 100005;
long long a[N], A[N], S[N];
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 check(long long mid) {
  mid--;
  long long j = 1, ans = 0;
  for (int i = (int)(1); i <= (int)(N - 1); i++)
    if (a[i])
      if (S[i] <= mid)
        ans += 1ll * a[i] * A[i - 1] + 1ll * a[i] * (a[i] + 1) / 2;
      else {
        long long s = 1;
        for (; j < i && s <= a[i];)
          if (S[i - 1] - S[j] + i * s > mid)
            j++;
          else {
            long long s1 = min((mid - S[i - 1] + S[j]) / i, 1ll * a[i]) + 1;
            ans += f(-i, mid - S[i - 1] + S[j] - i * s, j, s1 - s - 1);
            ans -=
                f(-i, mid - S[i - 1] + S[j] - i * s - a[j] * j, j, s1 - s - 1);
            ans += 1ll * (s1 - s) * (A[i - 1] - A[j]);
            ans += 1ll * (s + s1 - 1) * (s1 - s) / 2;
            if ((s = s1) <= a[i]) j++;
          }
        if (j == i) ans += work(s, a[i], mid / i);
      }
  return ans;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int n, tp;
pair<int, int> q[50];
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) {
    int x;
    scanf("%d", &x);
    q[++tp] = pair<int, int>(x, i);
    for (int j = (int)(tp - 1); j >= (int)(1); j--)
      q[j].first = gcd(q[j].first, x);
    int tmp = 1;
    for (int j = (int)(2); j <= (int)(tp); j++)
      if (q[j].first != q[j - 1].first) q[++tmp] = q[j];
    tp = tmp;
    for (int j = (int)(1); j <= (int)(tp); j++)
      a[q[j].first] += (j == tp ? i + 1 : q[j + 1].second) - q[j].second;
  }
  for (int i = (int)(1); i <= (int)(N - 1); i++) {
    A[i] = A[i - 1] + a[i];
    S[i] = S[i - 1] + 1ll * a[i] * i;
  }
  long long P = 1ll * n * (n + 1) / 2;
  P = P * (P + 1) / 2;
  P = (P + 1) / 2;
  long long l = 1, r = S[N - 1], ans = 0;
  while (l <= r) {
    long long mid = (l + r) / 2;
    if (check(mid) < P)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  printf("%lld\n", ans);
}
