#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
const int MAXN = 5e4 + 50;
long long a[MAXN], n;
void readInput() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
}
struct Node {
  long long val, count;
};
const int MAXA = 1e5 + 50;
long long bcnt[MAXA];
void findBcnt() {
  vector<Node> prev;
  prev.push_back({a[1], 1LL});
  bcnt[a[1]] += 1;
  for (int i = 2; i <= n; i++) {
    vector<Node> cur;
    cur.push_back({a[i], 1LL});
    for (const auto &e : prev) {
      long long nval = gcd(e.val, a[i]);
      if (cur.empty() || nval != cur.back().val) cur.push_back({nval, 0});
      cur.back().count += e.count;
    }
    for (const auto &e : cur) bcnt[e.val] += e.count;
    prev = cur;
  }
}
long long f(long long a, long long b, long long c) {
  if (c <= 0) return 0;
  if (a < b) swap(a, b);
  long long m = c / a;
  if (a == b)
    return m * (m - 1) / 2;
  else {
    long long k = (a - 1) / b, h = (c - a * m) / b;
    return f(b, a - b * k, c - b * (k * m + h)) + k * m * (m - 1) / 2 + m * h;
  }
}
inline long long g(long long a, long long b, long long c, long long X,
                   long long Y) {
  return f(a, b, c) - f(a, b, c - a * X) - f(a, b, c - b * Y) +
         f(a, b, c - a * X - b * Y);
}
vector<Node> b;
long long psum[MAXA], csum[MAXA], m;
inline long long rangeSum(int l, int r) {
  if (r < l) return 0;
  return psum[r] - psum[l - 1];
}
inline long long rangeCount(int l, int r) {
  if (r < l) return 0;
  return csum[r] - csum[l - 1];
}
inline long long countSegment(int l, int r, long long k) {
  long long mx = k - rangeSum(l + 1, r - 1);
  return g(b[l].val, b[r].val, mx, b[l].count, b[r].count);
}
long long findPos(long long k) {
  long long cnt = 0;
  int l = 1, r = 1;
  while (r + 1 <= m && rangeSum(l, r + 1) <= k) r++;
  for (l = 1; l <= m; l++) {
    long long t = min(b[l].count, k / b[l].val);
    cnt += t * (2 * b[l].count - t + 1) / 2;
    cnt += b[l].count * rangeCount(l + 1, r);
    if (l == m) continue;
    long long nr = max(l + 1, r);
    while (nr + 1 <= m && rangeSum(l + 1, nr + 1) <= k) nr++;
    for (int i = r + 1; i <= min(m, nr + 1); i++) cnt += countSegment(l, i, k);
    r = nr;
  }
  return cnt;
}
long long solve() {
  b.push_back({0, 0});
  for (long long x = 1; x < MAXA; x++)
    if (bcnt[x]) b.push_back({x, bcnt[x]});
  m = (long long)b.size() - 1;
  for (int i = 1; i <= m; i++) psum[i] = psum[i - 1] + (b[i].val * b[i].count);
  for (int i = 1; i <= m; i++) csum[i] = csum[i - 1] + b[i].count;
  long long nb = n * (n + 1) / 2;
  long long nc = nb * (nb + 1) / 2;
  long long low = 1, high = 1e15, res = -1;
  while (low <= high) {
    long long mid = (low + high) / 2;
    if (findPos(mid) < (nc + 1) / 2) {
      low = mid + 1;
    } else {
      res = mid;
      high = mid - 1;
    }
  }
  return res;
}
int main() {
  readInput();
  findBcnt();
  printf("%lld\n", solve());
}
