#include <bits/stdc++.h>
using namespace std;
int n;
int a[110000];
vector<int> DIV[110000], cong[110000];
long long gcd1[110000], gcd[110000], S[110000], sum[110000];
int mu[110000], primes[110000], used[110000];
int len;
int pre[110000], size[110000];
long long M;
long long mycalc(long long n, long long a, long long b, long long c) {
  long long ret = 0;
  if (!n) return ret;
  if (c < 0) {
    long long t = (a - c - 1) / a;
    ret -= t * n;
    c += t * a;
  }
  if (c / a > 0 || b / a > 0) {
    ret += c / a * n;
    ret += b / a * n * (n + 1) / 2;
    c %= a;
    b %= a;
  }
  long long newn = (b * n + c) / a;
  ret += newn * (n + 1);
  ret -= mycalc(newn, b, a, b - c - 1);
  return ret;
}
long long calc(long long a, long long b, long long c) {
  if (c < 0) return 0;
  long long minn = (c - a) / b, tmp = (b + a - 1) / a;
  long long ans = 0;
  ans -= tmp * (minn + 1) * minn / 2;
  ans += c / a + c / b + 1;
  return ans + mycalc(minn, a, tmp * a - b, c);
}
long long calc(long long A, long long B, long long C, long long X,
               long long Y) {
  X--;
  Y--;
  C -= A + B;
  return calc(A, B, C) - calc(A, B, C - A * (X + 1)) -
         calc(A, B, C - B * (Y + 1)) +
         calc(A, B, C - A * (X + 1) - B * (Y + 1));
}
long long calc(long long X) {
  long long ans = 0, upper = 0;
  int h = 1, h1 = 1;
  for (int i = 1; i <= 100000; i++) {
    long long ll = min(gcd[i], X / i);
    ans += (gcd[i] + gcd[i] - ll + 1) * (ll) / 2;
    while (h < 100000 && sum[h + 1] - sum[i - 1] <= X) {
      h++;
    }
    if (h >= i) ans += gcd[i] * (S[h] - S[i]);
    while (h1 < 100000 && sum[h1] - sum[i] <= X) {
      h1++;
    }
    for (int j = max(i, h) + 1; j <= h1; j++) {
      upper += 1LL * gcd[i] * gcd[j];
    }
  }
  if (ans + upper < (M + 1) / 2) return ans;
  h = 1;
  h1 = 1;
  for (int i = 1; i <= 100000; i++) {
    while (h < 100000 && sum[h + 1] - sum[i - 1] <= X) {
      h++;
    }
    while (h1 < 100000 && sum[h1] - sum[i] <= X) {
      h1++;
    }
    for (int j = max(i, h) + 1; j <= h1; j++) {
      ans += calc(i, j, X - sum[j - 1] + sum[i], gcd[i], gcd[j]);
    }
    if (ans >= (M + 1) / 2) return ans;
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= 100000; i++)
    for (int j = i; j <= 100000; j += i) DIV[j].push_back(i);
  int ma = 0;
  for (int i = 1; i <= 100000; i++)
    if (DIV[i].size() > ma) {
      ma = DIV[i].size();
    }
  for (int i = 1; i <= n; i++) {
    for (auto x : DIV[a[i]]) {
      if (pre[x] == i - 1) {
        size[x]++;
      } else {
        size[x] = 1;
      }
      gcd1[x] += size[x];
      pre[x] = i;
    }
  }
  mu[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    if (!used[i]) primes[++len] = i, mu[i] = -1;
    for (int j = 1; j <= len && i * primes[j] <= 100000; j++)
      if (i % primes[j] == 0) {
        used[i * primes[j]] = true;
        mu[i * primes[j]] = 0;
        break;
      } else {
        used[i * primes[j]] = true;
        mu[i * primes[j]] = -mu[i];
      }
  }
  for (int i = 1; i <= 100000; i++)
    for (int j = i; j <= 100000; j += i) gcd[i] += mu[j / i] * gcd1[j];
  long long m = 1LL * n * (n + 1) / 2;
  M = m * (m + 1) / 2;
  for (int i = 1; i <= 100000; i++) sum[i] = sum[i - 1] + 1LL * gcd[i] * i;
  for (int i = 1; i <= 100000; i++) S[i] = S[i - 1] + gcd[i];
  long long q = 0, h = 100000LL * m + 1e9, mid;
  while (q < h - 1) {
    mid = (q + h) / 2;
    if (calc(mid) >= (M + 1) / 2)
      h = mid;
    else
      q = mid;
  }
  cout << h << endl;
}
