#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const long long inf = 1e15;
int n;
int a[maxn];
vector<int> dvs[maxn], vec[maxn];
long long cnt[maxn];
void solve1() {
  for (int i = 1; i < maxn; i++)
    for (int j = i; j < maxn; j += i) dvs[j].push_back(i);
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    for (int y : dvs[x]) vec[y].push_back(i);
  }
  for (int i = 1; i < maxn; i++) {
    int bef = -10, c = 0;
    for (int x : vec[i]) {
      if (bef + 1 == x)
        bef++, c++;
      else
        cnt[i] += 1ll * c * (c + 1) / 2, bef = x, c = 1;
    }
    cnt[i] += 1ll * c * (c + 1) / 2;
  }
  for (int i = maxn - 1; i >= 1; i--) {
    for (int j = 2 * i; j < maxn; j += i) cnt[i] -= cnt[j];
  }
}
long long solve_eq(long long a, long long b, long long c) {
  if (c < 0) return 0;
  if (a > b) swap(a, b);
  long long B = c / b, A = (c - B * b) / a, BA = b / a;
  return solve_eq(a, b - BA * a, c - a * (B * BA + A + 1)) + (A + 1) * (B + 1) +
         BA * B * (B + 1) / 2;
}
long long f(int a, long long ca, int b, long long cb, long long lim) {
  if (ca <= 0 || cb <= 0 || lim < a + b) return 0;
  lim -= a + b;
  return solve_eq(a, b, lim) - solve_eq(a, b, lim - 1ll * a * ca) -
         solve_eq(a, b, lim - 1ll * b * cb) +
         solve_eq(a, b, lim - 1ll * a * ca - 1ll * b * cb);
}
long long solve2(long long num) {
  long long ans = 0, sum = 0, totc = 0;
  int pt = 0;
  for (int i = 1; i < maxn; i++) {
    if (cnt[i] == 0) continue;
    sum += 1ll * cnt[i] * i;
    totc += cnt[i];
    if (pt != 0) --pt, sum += 1ll * cnt[pt] * pt, totc += cnt[pt];
    while (pt < i && sum > num) {
      ans += f(pt, cnt[pt], i, cnt[i],
               num - sum + 1ll * pt * cnt[pt] + 1ll * i * cnt[i]);
      sum -= 1ll * cnt[pt] * pt;
      totc -= cnt[pt];
      pt++;
    }
    ans += 1ll * cnt[i] * (totc - cnt[i]);
    long long mxc = num / i;
    if (mxc >= cnt[i])
      ans += 1ll * cnt[i] * (cnt[i] + 1) / 2;
    else
      ans += mxc * cnt[i] - (mxc * (mxc - 1) / 2);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  solve1();
  long long l = 0, r = inf;
  long long N = 1ll * n * (n + 1) / 2;
  N = N * (N + 1) / 2;
  while (r - l > 1) {
    long long mid = (l + r) >> 1;
    if (solve2(mid) >= ((N + 1) / 2))
      r = mid;
    else
      l = mid;
  }
  return cout << r << endl, 0;
}
