#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int Prime[N + 5], mu[N + 5], num, n, a[N + 5], maxn = 0, cnt[N], has[N], sta[N],
                                               top = 0;
bool notPrime[N + 5];
vector<int> d[N + 5], s;
long long ans = 0;
void init() {
  memset(notPrime, false, sizeof notPrime);
  num = 0;
  mu[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!notPrime[i]) {
      Prime[++num] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= num && 1LL * Prime[j] * i <= N; j++) {
      notPrime[i * Prime[j]] = true;
      if (i % Prime[j] == 0) {
        mu[i * Prime[j]] = 0;
        break;
      }
      mu[i * Prime[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) d[j].push_back(i);
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline void read(int &x) {
  x = 0;
  int f = 1, c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
  x *= f;
}
int main() {
  init();
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), maxn = max(a[i], maxn), has[a[i]]++;
  for (int g = 1; g <= maxn; g++) {
    s.clear();
    for (int i = g; i <= maxn; i += g)
      for (int j = 1; j <= has[i]; j++) s.push_back(i / g);
    sort(s.begin(), s.end());
    for (int i = s.size() - 1; ~i; i--) {
      int tot = 0, x = s[i];
      for (unsigned int j = 0; j < d[x].size(); j++)
        tot += mu[d[x][j]] * cnt[d[x][j]];
      while (tot) {
        int y = sta[top--];
        if (gcd(x, y) == 1) ans = max(ans, 1LL * x * y * g), tot--;
        for (unsigned int j = 0; j < d[y].size(); j++) cnt[d[y][j]]--;
      }
      sta[++top] = x;
      for (unsigned int j = 0; j < d[x].size(); j++) cnt[d[x][j]]++;
    }
    while (top) {
      int x = sta[top--];
      for (unsigned int i = 0; i < d[x].size(); i++) cnt[d[x][i]]--;
    }
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Create a solution in cpp for 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 + 5;
int Prime[N + 5], mu[N + 5], num, n, a[N + 5], maxn = 0, cnt[N], has[N], sta[N],
                                               top = 0;
bool notPrime[N + 5];
vector<int> d[N + 5], s;
long long ans = 0;
void init() {
  memset(notPrime, false, sizeof notPrime);
  num = 0;
  mu[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!notPrime[i]) {
      Prime[++num] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= num && 1LL * Prime[j] * i <= N; j++) {
      notPrime[i * Prime[j]] = true;
      if (i % Prime[j] == 0) {
        mu[i * Prime[j]] = 0;
        break;
      }
      mu[i * Prime[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) d[j].push_back(i);
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline void read(int &x) {
  x = 0;
  int f = 1, c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
  x *= f;
}
int main() {
  init();
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), maxn = max(a[i], maxn), has[a[i]]++;
  for (int g = 1; g <= maxn; g++) {
    s.clear();
    for (int i = g; i <= maxn; i += g)
      for (int j = 1; j <= has[i]; j++) s.push_back(i / g);
    sort(s.begin(), s.end());
    for (int i = s.size() - 1; ~i; i--) {
      int tot = 0, x = s[i];
      for (unsigned int j = 0; j < d[x].size(); j++)
        tot += mu[d[x][j]] * cnt[d[x][j]];
      while (tot) {
        int y = sta[top--];
        if (gcd(x, y) == 1) ans = max(ans, 1LL * x * y * g), tot--;
        for (unsigned int j = 0; j < d[y].size(); j++) cnt[d[y][j]]--;
      }
      sta[++top] = x;
      for (unsigned int j = 0; j < d[x].size(); j++) cnt[d[x][j]]++;
    }
    while (top) {
      int x = sta[top--];
      for (unsigned int i = 0; i < d[x].size(); i++) cnt[d[x][i]]--;
    }
  }
  printf("%lld", ans);
  return 0;
}

```