#include <bits/stdc++.h>
using namespace std;
int arr[100005];
vector<int> v[100005];
int h[100005];
int mu[100005];
int spf[100005];
vector<int> fac[100005];
long long ans;
void sieve() {
  for (int i = 0; i < 100005; i++) {
    spf[i] = i;
  }
  for (int i = 2; i < 100005; ++i) {
    if (spf[i] != i) continue;
    for (long long j = 2 * i; j < 100005; j += i) {
      if (spf[j] == j) spf[j] = i;
    }
  }
}
int cnt[100005];
void upd(int i, int val) {
  for (auto j : fac[i]) {
    cnt[j] += val;
  }
}
bool calc(int i) {
  int ans = 0;
  for (auto j : fac[i]) {
    ans += cnt[j] * mu[j];
  }
  return ans > 0;
}
void solve(int y) {
  stack<int> s;
  for (auto i : v[y]) {
    while (calc(i)) {
      int z = s.top();
      upd(z, -1);
      ans = max(ans, 1LL * z * i * y);
      s.pop();
    }
    upd(i, 1);
    s.push(i);
  }
  while (!s.empty()) {
    int z = s.top();
    upd(z, -1);
    s.pop();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int n;
  cin >> n;
  for (int i = 1; i < n + 1; i++) {
    cin >> arr[i];
    h[arr[i]] = 1;
    ans = max(ans, 1ll * arr[i]);
  }
  mu[1] = 1;
  sieve();
  for (int i = 2; i < 100005; i++) {
    int x = spf[i];
    int y = i;
    y /= x;
    if (spf[y] == x) {
      mu[i] = 0;
    } else
      mu[i] = -1 * mu[y];
  }
  for (int i = 1; i < 100005; i++) {
    int z = sqrt(i);
    for (int j = 1; j < z + 1; j++) {
      if (i % j != 0) continue;
      fac[i].push_back(j);
      if (i / j != j) {
        fac[i].push_back(i / j);
      }
    }
  }
  for (int i = 1; i < 100005; i++) {
    if (h[i] == 0) continue;
    for (auto j : fac[i]) {
      v[j].push_back(i / j);
    }
  }
  for (int i = 1; i < 100005; i++) {
    sort(v[i].begin(), v[i].end(), greater<int>());
    solve(i);
  }
  cout << ans;
}

### Prompt

Your task is to create 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;
int arr[100005];
vector<int> v[100005];
int h[100005];
int mu[100005];
int spf[100005];
vector<int> fac[100005];
long long ans;
void sieve() {
  for (int i = 0; i < 100005; i++) {
    spf[i] = i;
  }
  for (int i = 2; i < 100005; ++i) {
    if (spf[i] != i) continue;
    for (long long j = 2 * i; j < 100005; j += i) {
      if (spf[j] == j) spf[j] = i;
    }
  }
}
int cnt[100005];
void upd(int i, int val) {
  for (auto j : fac[i]) {
    cnt[j] += val;
  }
}
bool calc(int i) {
  int ans = 0;
  for (auto j : fac[i]) {
    ans += cnt[j] * mu[j];
  }
  return ans > 0;
}
void solve(int y) {
  stack<int> s;
  for (auto i : v[y]) {
    while (calc(i)) {
      int z = s.top();
      upd(z, -1);
      ans = max(ans, 1LL * z * i * y);
      s.pop();
    }
    upd(i, 1);
    s.push(i);
  }
  while (!s.empty()) {
    int z = s.top();
    upd(z, -1);
    s.pop();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int n;
  cin >> n;
  for (int i = 1; i < n + 1; i++) {
    cin >> arr[i];
    h[arr[i]] = 1;
    ans = max(ans, 1ll * arr[i]);
  }
  mu[1] = 1;
  sieve();
  for (int i = 2; i < 100005; i++) {
    int x = spf[i];
    int y = i;
    y /= x;
    if (spf[y] == x) {
      mu[i] = 0;
    } else
      mu[i] = -1 * mu[y];
  }
  for (int i = 1; i < 100005; i++) {
    int z = sqrt(i);
    for (int j = 1; j < z + 1; j++) {
      if (i % j != 0) continue;
      fac[i].push_back(j);
      if (i / j != j) {
        fac[i].push_back(i / j);
      }
    }
  }
  for (int i = 1; i < 100005; i++) {
    if (h[i] == 0) continue;
    for (auto j : fac[i]) {
      v[j].push_back(i / j);
    }
  }
  for (int i = 1; i < 100005; i++) {
    sort(v[i].begin(), v[i].end(), greater<int>());
    solve(i);
  }
  cout << ans;
}

```