#include <bits/stdc++.h>
using namespace std;
struct data {
  long long sum;
  int num;
};
int a[100010], gcd[100010][20], ch[100010], lg, cnt;
long long sum[100010], pre[2][100010];
data A[100010];
int calc(int a, int b) {
  int y = a % b;
  while (y) {
    a = b;
    b = y;
    y = a % b;
  }
  return b;
}
int get_gcd(int l, int r) {
  int len = r - l + 1;
  return calc(gcd[l][ch[len]], gcd[r - (1 << ch[len]) + 1][ch[len]]);
}
long long get_sum(long long x) { return x * (x + 1) / 2; }
long long get_res(long long n, long long a, long long b, long long c) {
  long long res = 0;
  if (a < 0) {
    long long need = (-a) / c + 1;
    res -= need * get_sum(n);
    a += need * c;
  }
  if (b < 0) {
    long long need = (-b) / c + 1;
    res -= need * (n + 1);
    b += need * c;
  }
  if (a >= c || b >= c) {
    long long t1 = a / c, t2 = b / c;
    res += t1 * get_sum(n) + t2 * (n + 1);
    a %= c;
    b %= c;
  }
  if (a == 0) return res + (b / c) * (n + 1);
  if (a * n + b < c) return res;
  long long mx = (a * n + b) / c;
  res += mx * (n + 1) - get_res(mx - 1, c, c - b + a - 1, a);
  return res;
}
long long solve(long long x) {
  long long res = 0;
  for (int i = 1; i <= cnt; i++) {
    long long mx = min(A[i].sum, x / A[i].num);
    if (mx == 0) continue;
    res += (A[i].sum + 1) * mx - get_sum(mx);
  }
  int cur = 1;
  for (int i = 1; i <= cnt - 1; i++) {
    if (cur == i && cur != cnt + 1) cur++;
    long long rem = A[i].sum;
    if (cur == i + 1) {
      long long tmp = max(0LL, (x - A[i + 1].num) / A[i].num);
      rem = min(rem, tmp);
    }
    while (rem) {
      if (cur == cnt + 1) {
        res += (pre[0][cur - 1] - pre[0][i]) * rem + get_sum(rem);
        rem = 0;
      } else {
        long long tmp = (x - (pre[1][cur] - pre[1][i])) / A[i].num;
        if (tmp > rem)
          cur++;
        else {
          if (tmp <= 0) tmp = 1;
          long long alr = pre[1][cur - 1] - pre[1][i];
          res += (pre[0][cur - 1] - pre[0][i]) * (rem - tmp + 1);
          res += get_res(rem, -A[i].num, x - alr, A[cur].num) -
                 get_res(tmp - 1, -A[i].num, x - alr, A[cur].num);
          rem = tmp - 1;
        }
      }
    }
  }
  return res;
}
int main() {
  int n, mx = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    gcd[i][0] = a[i];
    mx = max(mx, a[i]);
  }
  int tmp = 1;
  ch[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (tmp < i) {
      tmp *= 2;
      lg++;
    }
    ch[i] = lg - 1;
  }
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= n; i++) {
      if (i + (1 << j) - 1 > n) break;
      gcd[i][j] = calc(gcd[i][j - 1], gcd[i + (1 << j - 1)][j - 1]);
    }
  for (int i = 1; i <= n; i++) {
    int cur = i;
    while (cur != n + 1) {
      int now = get_gcd(i, cur), lef = cur, righ = n, ch;
      while (lef <= righ) {
        int mid = (lef + righ) / 2;
        if (get_gcd(i, mid) == now) {
          ch = mid;
          lef = mid + 1;
        } else
          righ = mid - 1;
      }
      sum[now] += ch - cur + 1;
      cur = ch + 1;
    }
  }
  for (int i = 1; i <= mx; i++)
    if (sum[i]) A[++cnt] = (data){sum[i], i};
  for (int i = 1; i <= cnt; i++) {
    pre[0][i] = pre[0][i - 1] + A[i].sum;
    pre[1][i] = pre[1][i - 1] + A[i].sum * A[i].num;
  }
  long long lef = 0, righ = pre[1][cnt], need = (get_sum(pre[0][cnt]) + 1) / 2,
            ch;
  while (lef <= righ) {
    long long mid = (lef + righ) / 2;
    if (solve(mid) >= need) {
      ch = mid;
      righ = mid - 1;
    } else
      lef = mid + 1;
  }
  printf("%lld\n", ch);
  return 0;
}
