#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
auto& errStream = cerr;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    ll g = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
  }
}
vector<pi> Cmp(vector<pi> x) {
  vector<pi> y;
  for (auto v : x) {
    if (y.empty() || y.back().first != v.first) y.push_back(pi(v.first, 0));
    y.back().second += v.second;
  }
  return y;
}
vector<pi> Waf() {
  ll n = read();
  vi a(n);
  for (ll i = ll(0); i < ll(n); i++) a[i] = read();
  vector<pi> res;
  vector<pi> w;
  for (ll i = ll(0); i < ll(n); i++) {
    for (auto& v : w) v.first = gcd(v.first, a[i]);
    w.push_back(pi(a[i], 1));
    w = Cmp(w);
    res.insert(res.end(), w.begin(), w.end());
  }
  sort(res.begin(), res.end());
  return Cmp(res);
}
ll gauss_sum(ll n, ll a, ll b, ll c) {
  if (n == 0) return 0;
  ll res = 0;
  {
    ll p = a / c;
    res += n * (n - 1) / 2 * p;
    a %= c;
  }
  {
    ll p = b / c;
    res += n * p;
    b %= c;
  }
  if (a == 0) return res;
  ll top = (a * (n - 1) + b) / c;
  res += top * n;
  ll h = (b + 1 + c - 1) / c;
  if (h <= top)
    res -= gauss_sum(top - h + 1, c, c * h - (b + 1), a) + top - h + 1;
  return res;
}
ll Cnt(const vi& val, const vi& cnt, const ll m) {
  ll len = accumulate(cnt.begin(), cnt.end(), ll(0));
  ll n = val.size();
  ll li = 0, lj = 0, lk = 0, ri = 0, rj = 0, rk = 0, cur = 0, sum = 0;
  while (lk < len) {
    if (ri < n) {
      ll rem = cnt[ri] - rj;
      if (cur + rem * val[ri] <= m) {
        cur += rem * val[ri];
        ri++;
        rj = 0;
        rk += rem;
        continue;
      } else {
        {
          ll num = (m - cur) / val[ri];
          cur += num * val[ri];
          rj += num;
          rk += num;
          rem -= num;
        }
        ll steps;
        if (cur - val[li] * (cnt[li] - 1 - lj) + rem * val[ri] <= m) {
          ll hoge = cur + rem * val[ri] - m;
          steps = (hoge + val[li] - 1) / val[li];
        } else {
          steps = cnt[li] - lj;
        }
        sum += (rk - lk) * steps;
        sum -= steps * (steps - 1) / 2;
        sum += gauss_sum(steps, val[li], m - cur, val[ri]);
        cur -= steps * val[li];
        lj += steps;
        if (lj == cnt[li]) {
          li++;
          lj = 0;
        }
        lk += steps;
      }
    } else {
      ll rem = len - lk;
      sum += rem * (rem + 1) / 2;
      li = n;
      lj = 0;
      lk = len;
    }
  }
  return sum;
}
signed main() {
  auto w = Waf();
  cerrDummy << w << endl;
  vi val, cnt;
  for (auto v : w) {
    val.push_back(v.first);
    cnt.push_back(v.second);
  }
  ll len = accumulate(cnt.begin(), cnt.end(), ll(0));
  len = len * (len + 1) / 2;
  ll m = (len - 1) / 2;
  ll l = 1, r = 1;
  for (ll i = ll(0); i < ll(val.size()); i++) r += val[i] * cnt[i];
  while (r - l > 1) {
    const ll mid = (l + r) / 2;
    if (Cnt(val, cnt, mid - 1) <= m)
      l = mid;
    else
      r = mid;
  }
  print(l);
}
