#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int n, m = 100000, a[N], b[N], prm[N], pm[N], tt, mu[N], st[N], tp, c[N], q[N],
       tq;
vector<int> dd[N];
long long ans;
void dfs(int o, int ns, int xx) {
  if (o > tq) {
    dd[xx].push_back(ns);
    return;
  }
  dfs(o + 1, ns, xx), dfs(o + 1, ns * q[o], xx);
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
  mu[1] = 1;
  for (int i = 2; i <= N - 5; ++i) {
    if (!pm[i]) pm[i] = prm[++tt] = i, mu[i] = -1;
    for (int j = 1; i * prm[j] <= N - 5; ++j) {
      pm[i * prm[j]] = prm[j], mu[i * prm[j]] = -mu[i];
      if (i % prm[j] == 0) {
        mu[i * prm[j]] = 0;
        break;
      }
    }
  }
  n = rd();
  while (n--) ++b[rd()];
  for (int i = m; i; --i) {
    if (!b[i]) continue;
    if (b[i] > 1) ans = max(ans, 1ll * i);
    int x = i;
    while (x > 1) {
      int p = pm[x];
      b[i / p] |= 1;
      while (pm[x] == p) x /= p;
    }
  }
  n = 0;
  for (int i = 1; i <= m; ++i)
    if (b[i]) a[++n] = i;
  for (int i = n; i; --i) {
    tq = 0;
    int x = a[i], nn;
    while (x > 1) {
      int p = pm[x];
      q[++tq] = p;
      while (pm[x] == p) x /= p;
    }
    dfs(1, 1, a[i]);
    while (1) {
      int sx = 0;
      nn = dd[a[i]].size();
      for (int j = 0; j < nn; ++j) sx += mu[dd[a[i]][j]] * c[dd[a[i]][j]];
      if (!sx || (sx == 1 && gcd(a[i], st[tp]) == 1)) break;
      int y = st[tp];
      nn = dd[y].size();
      for (int j = 0; j < nn; ++j) --c[dd[y][j]];
      --tp;
    }
    if (gcd(a[i], st[tp]) == 1) ans = max(ans, 1ll * a[i] * st[tp]);
    st[++tp] = a[i];
    nn = dd[a[i]].size();
    for (int j = 0; j < nn; ++j) ++c[dd[a[i]][j]];
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

Given an array a, consisting of n integers, find:

$$$max_{1 ≤ i < j ≤ n} LCM(a_i,a_j),$$$

where LCM(x, y) is the smallest positive integer that is divisible by both x and y. For example, LCM(6, 8) = 24, LCM(4, 12) = 12, LCM(2, 3) = 6.

Input

The first line contains an integer n (2 ≤ n ≤ 10^5) — the number of elements in the array a.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^5) — the elements of the array a.

Output

Print one integer, the maximum value of the least common multiple of two elements in the array a.

Examples

Input


3
13 35 77


Output


1001

Input


6
1 2 4 8 16 32


Output


32

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int n, m = 100000, a[N], b[N], prm[N], pm[N], tt, mu[N], st[N], tp, c[N], q[N],
       tq;
vector<int> dd[N];
long long ans;
void dfs(int o, int ns, int xx) {
  if (o > tq) {
    dd[xx].push_back(ns);
    return;
  }
  dfs(o + 1, ns, xx), dfs(o + 1, ns * q[o], xx);
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
  mu[1] = 1;
  for (int i = 2; i <= N - 5; ++i) {
    if (!pm[i]) pm[i] = prm[++tt] = i, mu[i] = -1;
    for (int j = 1; i * prm[j] <= N - 5; ++j) {
      pm[i * prm[j]] = prm[j], mu[i * prm[j]] = -mu[i];
      if (i % prm[j] == 0) {
        mu[i * prm[j]] = 0;
        break;
      }
    }
  }
  n = rd();
  while (n--) ++b[rd()];
  for (int i = m; i; --i) {
    if (!b[i]) continue;
    if (b[i] > 1) ans = max(ans, 1ll * i);
    int x = i;
    while (x > 1) {
      int p = pm[x];
      b[i / p] |= 1;
      while (pm[x] == p) x /= p;
    }
  }
  n = 0;
  for (int i = 1; i <= m; ++i)
    if (b[i]) a[++n] = i;
  for (int i = n; i; --i) {
    tq = 0;
    int x = a[i], nn;
    while (x > 1) {
      int p = pm[x];
      q[++tq] = p;
      while (pm[x] == p) x /= p;
    }
    dfs(1, 1, a[i]);
    while (1) {
      int sx = 0;
      nn = dd[a[i]].size();
      for (int j = 0; j < nn; ++j) sx += mu[dd[a[i]][j]] * c[dd[a[i]][j]];
      if (!sx || (sx == 1 && gcd(a[i], st[tp]) == 1)) break;
      int y = st[tp];
      nn = dd[y].size();
      for (int j = 0; j < nn; ++j) --c[dd[y][j]];
      --tp;
    }
    if (gcd(a[i], st[tp]) == 1) ans = max(ans, 1ll * a[i] * st[tp]);
    st[++tp] = a[i];
    nn = dd[a[i]].size();
    for (int j = 0; j < nn; ++j) ++c[dd[a[i]][j]];
  }
  printf("%lld\n", ans);
  return 0;
}

```