#include <bits/stdc++.h>
using namespace std;
vector<int> vec[100000 + 5];
int mu[100000 + 5], pr[100000 + 5], mk[100000 + 5], cnt[100000 + 5], n, tot,
    ss[100000 + 5];
long long ans = -(1ll << 60);
stack<int> sta;
inline int get(int to) {
  int as = 0;
  for (int s : vec[to]) as += mu[s] * cnt[s];
  return as;
}
int main() {
  mu[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    if (!mk[i]) pr[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot; j++) {
      if (1ll * i * pr[j] > 100000) break;
      mk[i * pr[j]] = 1;
      if (i % pr[j] == 0) break;
      mu[i * pr[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= 100000; i++) {
    for (int j = 1; j * j <= i; j++) {
      if (i % j == 0) {
        vec[i].push_back(j);
        if (j * j != i) vec[i].push_back(i / j);
      }
    }
  }
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++)
    scanf("%d", &x), ss[x] = 1, ans = max(ans, 1ll * x);
  for (int i = 1; i <= 100000; i++) {
    for (int j = 2; i * j <= 100000; j++) ss[i] |= ss[i * j];
  }
  for (int i = 100000, tp = 0; i >= 1; i--) {
    if (!ss[i]) continue;
    tp = 0;
    while (get(i)) {
      tp = sta.top(), sta.pop();
      for (int j : vec[tp]) --cnt[j];
    }
    ans = max(ans, 1ll * tp * i), sta.push(i);
    for (int j : vec[i]) ++cnt[j];
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Please formulate 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;
vector<int> vec[100000 + 5];
int mu[100000 + 5], pr[100000 + 5], mk[100000 + 5], cnt[100000 + 5], n, tot,
    ss[100000 + 5];
long long ans = -(1ll << 60);
stack<int> sta;
inline int get(int to) {
  int as = 0;
  for (int s : vec[to]) as += mu[s] * cnt[s];
  return as;
}
int main() {
  mu[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    if (!mk[i]) pr[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot; j++) {
      if (1ll * i * pr[j] > 100000) break;
      mk[i * pr[j]] = 1;
      if (i % pr[j] == 0) break;
      mu[i * pr[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= 100000; i++) {
    for (int j = 1; j * j <= i; j++) {
      if (i % j == 0) {
        vec[i].push_back(j);
        if (j * j != i) vec[i].push_back(i / j);
      }
    }
  }
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++)
    scanf("%d", &x), ss[x] = 1, ans = max(ans, 1ll * x);
  for (int i = 1; i <= 100000; i++) {
    for (int j = 2; i * j <= 100000; j++) ss[i] |= ss[i * j];
  }
  for (int i = 100000, tp = 0; i >= 1; i--) {
    if (!ss[i]) continue;
    tp = 0;
    while (get(i)) {
      tp = sta.top(), sta.pop();
      for (int j : vec[tp]) --cnt[j];
    }
    ans = max(ans, 1ll * tp * i), sta.push(i);
    for (int j : vec[i]) ++cnt[j];
  }
  printf("%lld", ans);
  return 0;
}

```