#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N], b[N], cnt, d, i, j, k, x, y, p[N], l, u[N];
bool v[N], vis[N];
long long ans, w[N], ww[N], tot;
vector<int> vct[N];
int main() {
  u[1] = 1;
  for (i = 2; i <= 100000; ++i) {
    if (!vis[i]) {
      p[++l] = i;
      u[i] = -1;
    }
    for (j = 1; j <= l && p[j] * i <= 100000; ++j) {
      vis[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
      else
        u[p[j] * i] = -u[i];
    }
  }
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    ans = max(ans, 1ll * a[i]);
    v[a[i]] = true;
  }
  for (i = 1; i <= 100000; ++i)
    for (j = i; j <= 100000; j += i) vct[j].push_back(i);
  for (d = 1; d <= 100000; ++d) {
    cnt = 0;
    for (i = d; i <= 100000; i += d)
      if (v[i]) b[++cnt] = i / d;
    if (cnt <= 1) continue;
    tot = 0;
    for (j = 1; j <= cnt; ++j)
      for (x = vct[b[j]].size() - 1; x >= 0; --x) ww[vct[b[j]][x]] += b[j];
    for (i = cnt, j = 1; i >= j && 1ll * d * b[i] * b[cnt] > ans; --i) {
      for (x = vct[b[i]].size() - 1; x >= 0; --x)
        w[k = vct[b[i]][x]] += b[i], tot += u[k] * b[i] * ww[k];
      while (j <= cnt && tot > 0) {
        for (x = vct[b[j]].size() - 1; x >= 0; --x)
          ww[k = vct[b[j]][x]] -= b[j], tot -= u[k] * b[j] * w[k];
        ++j;
      }
      ans = max(ans, 1ll * d * b[i] * b[j - 1]);
    }
    while (j <= cnt) {
      for (x = vct[b[j]].size() - 1; x >= 0; --x) ww[vct[b[j]][x]] -= b[j];
      ++j;
    }
    for (++i; i <= cnt; ++i) {
      for (x = vct[b[i]].size() - 1; x >= 0; --x) w[vct[b[i]][x]] -= b[i];
    }
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Please create a solution in cpp 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 = 100005;
int n, a[N], b[N], cnt, d, i, j, k, x, y, p[N], l, u[N];
bool v[N], vis[N];
long long ans, w[N], ww[N], tot;
vector<int> vct[N];
int main() {
  u[1] = 1;
  for (i = 2; i <= 100000; ++i) {
    if (!vis[i]) {
      p[++l] = i;
      u[i] = -1;
    }
    for (j = 1; j <= l && p[j] * i <= 100000; ++j) {
      vis[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
      else
        u[p[j] * i] = -u[i];
    }
  }
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    ans = max(ans, 1ll * a[i]);
    v[a[i]] = true;
  }
  for (i = 1; i <= 100000; ++i)
    for (j = i; j <= 100000; j += i) vct[j].push_back(i);
  for (d = 1; d <= 100000; ++d) {
    cnt = 0;
    for (i = d; i <= 100000; i += d)
      if (v[i]) b[++cnt] = i / d;
    if (cnt <= 1) continue;
    tot = 0;
    for (j = 1; j <= cnt; ++j)
      for (x = vct[b[j]].size() - 1; x >= 0; --x) ww[vct[b[j]][x]] += b[j];
    for (i = cnt, j = 1; i >= j && 1ll * d * b[i] * b[cnt] > ans; --i) {
      for (x = vct[b[i]].size() - 1; x >= 0; --x)
        w[k = vct[b[i]][x]] += b[i], tot += u[k] * b[i] * ww[k];
      while (j <= cnt && tot > 0) {
        for (x = vct[b[j]].size() - 1; x >= 0; --x)
          ww[k = vct[b[j]][x]] -= b[j], tot -= u[k] * b[j] * w[k];
        ++j;
      }
      ans = max(ans, 1ll * d * b[i] * b[j - 1]);
    }
    while (j <= cnt) {
      for (x = vct[b[j]].size() - 1; x >= 0; --x) ww[vct[b[j]][x]] -= b[j];
      ++j;
    }
    for (++i; i <= cnt; ++i) {
      for (x = vct[b[i]].size() - 1; x >= 0; --x) w[vct[b[i]][x]] -= b[i];
    }
  }
  printf("%lld", ans);
  return 0;
}

```