#include <bits/stdc++.h>
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;
template <class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
vector<int> mobius_all(int M) {
  vector<int> mobius(M), isprime(M);
  for (int i = 0; i < M; ++i) {
    mobius[i] = isprime[i] = 1;
  }
  for (int i = 2; i < M; ++i) {
    if (isprime[i]) {
      for (int j = i; j < M; j += i) {
        mobius[j] = -mobius[j];
        isprime[j] = 0;
      }
      isprime[i] = 1;
      ll x = (ll)i * i;
      if (x <= M) {
        for (int j = x; j < M; j += x) {
          mobius[j] = 0;
        }
      }
    }
  }
  return mobius;
}
int main() {
  int n;
  cin >> n;
  int M = 100001;
  vector<int> v(n), cnt(M), val(M);
  for (auto &&i : v) scanf("%d", &i), cnt[i] = 1;
  ll ans = *max_element(v.begin(), v.end());
  auto mobius = mobius_all(M);
  vector<int> isprime(M, 1);
  for (int i = 2; i < M; ++i) {
    if (isprime[i]) {
      for (int j = (M - 1) / i; j != 0; --j) {
        if (j != 1) isprime[j * i] = 0;
        cnt[j] |= cnt[j * i];
      }
    }
  }
  vector<vector<int>> div(M);
  for (int i = 1; i < M; ++i) {
    if (cnt[i]) {
      for (int j = i; j < M; j += i) {
        if (cnt[j]) div[j].emplace_back(i);
      }
    }
  }
  auto f = [&](int i) -> bool {
    int ret = 0;
    for (auto &&j : div[i]) ret += val[j];
    return ret != 0;
  };
  vector<int> st;
  for (int i = M - 1; i > 0; --i) {
    if (!cnt[i]) continue;
    while (f(i)) {
      ans = max(ans, (ll)i * st.back());
      for (auto &&j : div[st.back()]) val[j] -= mobius[j];
      st.pop_back();
    }
    for (auto &&j : div[i]) val[j] += mobius[j];
    st.emplace_back(i);
  }
  cout << ans << "\n";
  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>
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;
template <class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
vector<int> mobius_all(int M) {
  vector<int> mobius(M), isprime(M);
  for (int i = 0; i < M; ++i) {
    mobius[i] = isprime[i] = 1;
  }
  for (int i = 2; i < M; ++i) {
    if (isprime[i]) {
      for (int j = i; j < M; j += i) {
        mobius[j] = -mobius[j];
        isprime[j] = 0;
      }
      isprime[i] = 1;
      ll x = (ll)i * i;
      if (x <= M) {
        for (int j = x; j < M; j += x) {
          mobius[j] = 0;
        }
      }
    }
  }
  return mobius;
}
int main() {
  int n;
  cin >> n;
  int M = 100001;
  vector<int> v(n), cnt(M), val(M);
  for (auto &&i : v) scanf("%d", &i), cnt[i] = 1;
  ll ans = *max_element(v.begin(), v.end());
  auto mobius = mobius_all(M);
  vector<int> isprime(M, 1);
  for (int i = 2; i < M; ++i) {
    if (isprime[i]) {
      for (int j = (M - 1) / i; j != 0; --j) {
        if (j != 1) isprime[j * i] = 0;
        cnt[j] |= cnt[j * i];
      }
    }
  }
  vector<vector<int>> div(M);
  for (int i = 1; i < M; ++i) {
    if (cnt[i]) {
      for (int j = i; j < M; j += i) {
        if (cnt[j]) div[j].emplace_back(i);
      }
    }
  }
  auto f = [&](int i) -> bool {
    int ret = 0;
    for (auto &&j : div[i]) ret += val[j];
    return ret != 0;
  };
  vector<int> st;
  for (int i = M - 1; i > 0; --i) {
    if (!cnt[i]) continue;
    while (f(i)) {
      ans = max(ans, (ll)i * st.back());
      for (auto &&j : div[st.back()]) val[j] -= mobius[j];
      st.pop_back();
    }
    for (auto &&j : div[i]) val[j] += mobius[j];
    st.emplace_back(i);
  }
  cout << ans << "\n";
  return 0;
}

```