#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return (a % b == 0) ? b : gcd(b, a % b); }
inline long long S(long long n) { return n * (n + 1) >> 1; }
long long f(long long n, long long a, long long b, long long c) {
  if (!c) return 0;
  if (a >= c)
    return (a / c) * S(n - 1) + f(n, a % c, b, c);
  else if (b >= c)
    return (b / c) * n + f(n, a, b % c, c);
  else {
    long long m = (a * (n - 1) + b) / c;
    return n * m - f(m, c, c - b - 1, a);
  }
}
int fir[50005];
pair<int, long long> num[1500005], b[1500005];
long long sum1[1500005], sum2[1500005];
int pre(int n) {
  pair<int, long long> cur[50], t[50];
  int sz = 0, m = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= sz; j++)
      t[j] = pair<int, long long>(gcd(cur[j].first, fir[i]), cur[j].second);
    t[++sz] = pair<int, long long>(fir[i], i);
    int v = 0;
    for (int j = 1; j <= sz; j++)
      if (t[j].first != t[j - 1].first) cur[++v] = t[j];
    sz = v;
    cur[sz + 1] = pair<int, long long>(0, i + 1);
    for (int j = 1; j <= sz; j++)
      b[++m] =
          pair<int, long long>(cur[j].first, cur[j + 1].second - cur[j].second);
  }
  sort(b + 1, b + m + 1);
  sz = 0;
  for (int i = 1; i <= m; i++)
    if (b[i].first != b[i - 1].first)
      num[++sz] = b[i];
    else
      num[sz].second += b[i].second;
  for (int i = 1; i <= sz; i++) {
    sum1[i] = sum1[i - 1] + num[i].second;
    sum2[i] = sum2[i - 1] + num[i].first * num[i].second;
  }
  return sz;
}
long long check(int n, long long m) {
  long long ans = 0;
  bool ok = 0;
  int r = 0;
  for (int i = 1; i <= n; i++)
    if (sum2[i] > m) {
      int x = num[i].first;
      long long y = num[i].second, d = 1;
      if (x > m) {
        ans += sum1[i - 1] * y + S(y);
        continue;
      }
      if (!ok) {
        d = (m - sum2[i - 1] + x) / x;
        ok = 1;
      }
      while (d <= y) {
        long long s = sum2[i - 1] + d * x;
        while (s - sum2[r] > m) r++;
        long long v = min(y, d + (m + sum2[r] - s) / x);
        if (r)
          ans += sum1[r - 1] * (v - d + 1) +
                 f(v - d + 1, x, s - sum2[r - 1] - m + num[r].first - 1,
                   num[r].first);
        d = v + 1;
      }
    }
  return S(sum1[n]) - ans;
}
long long solve(int n) {
  long long l = 1, r = 1e16;
  while (l < r) {
    long long m = ((l + r) >> 1);
    if (check(n, m) >= ((S(sum1[n]) + 1) >> 1))
      r = m;
    else
      l = m + 1;
  }
  return l;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &fir[i]);
  int m = pre(n);
  printf("%lld\n", solve(m));
  return 0;
}
