#include <bits/stdc++.h>
using namespace std;
void _co() { cout << '\n'; }
template <typename T, typename... Ts>
void _co(const T &value, const Ts &...values) {
  cout << ' ' << value;
  _co(values...);
}
template <typename T, typename... Ts>
void co(const T &value, const Ts &...values) {
  cout << "deb: " << value;
  _co(values...);
}
const int N = 1e5 + 5;
using ll = long long;
const int M = N;
int primes[M];
int mobius[M];
void eratosthene() {
  for (int i = 2, lim = sqrt(M - 5); i <= lim; i++)
    if (primes[i] == 0) {
      for (int j = i * i; j <= M - 5; j += i) primes[j] = i;
    }
  for (int i = (2); i <= (M - 5); i++)
    if (primes[i] == 0) primes[i] = i;
}
int _mobius(int X) {
  int ret = 1;
  while (X > 1) {
    int u = primes[X];
    int cnt = 0;
    ret *= -1;
    while (X % u == 0) {
      X /= u;
      cnt++;
    }
    if (cnt >= 2) return 0;
  }
  return ret;
}
vector<int> divi[N], multi[N], a;
int n;
void prep() {
  eratosthene();
  for (int i = (1); i <= (N - 5); i++) mobius[i] = _mobius(i);
  for (int i = (1); i <= (N - 5); i++) {
    for (int j = i; j <= N - 5; j += i) divi[j].push_back(i);
  }
  for (auto &num : a) {
    for (auto &div : divi[num]) multi[div].push_back(num / div);
  }
  for (int i = (1); i <= (N - 5); i++) {
    vector<int> nx;
    for (auto &it : divi[i])
      if (mobius[it] != 0) nx.push_back(it);
    divi[i].swap(nx);
  }
}
int cnt[N];
void modify(int num, int dir) {
  for (auto &it : divi[num]) cnt[it] += dir;
}
ll countN(int num) {
  ll ret = 0;
  for (auto &it : divi[num]) {
    ret += mobius[it] * cnt[it];
  }
  return ret;
}
ll solve(int lab, vector<int> &inp) {
  ll ret = 0;
  stack<int> st;
  for (auto &it : inp) {
    int last = 0;
    while (!st.empty() && countN(it) != 0) {
      last = st.top();
      modify(last, -1);
      st.pop();
    }
    modify(it, 1);
    st.push(it);
    ret = max(ret, 1LL * it * last * lab);
  }
  while (!st.empty()) {
    int u = st.top();
    st.pop();
    modify(u, -1);
  }
  return ret;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll ans = 0;
  cin >> n;
  for (int i = (1); i <= (n); i++) {
    int t;
    cin >> t;
    a.push_back(t);
  }
  sort(a.begin(), a.end(), greater<int>());
  for (int i = (1); i <= (a.size() - 1); i++)
    if (a[i] == a[i - 1]) {
      ans = a[i];
      break;
    }
  a.resize(distance(a.begin(), unique(a.begin(), a.end())));
  prep();
  for (int i = (1); i <= (N - 5); i++) {
    ans = max(ans, solve(i, multi[i]));
  }
  cout << ans << '\n';
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
void _co() { cout << '\n'; }
template <typename T, typename... Ts>
void _co(const T &value, const Ts &...values) {
  cout << ' ' << value;
  _co(values...);
}
template <typename T, typename... Ts>
void co(const T &value, const Ts &...values) {
  cout << "deb: " << value;
  _co(values...);
}
const int N = 1e5 + 5;
using ll = long long;
const int M = N;
int primes[M];
int mobius[M];
void eratosthene() {
  for (int i = 2, lim = sqrt(M - 5); i <= lim; i++)
    if (primes[i] == 0) {
      for (int j = i * i; j <= M - 5; j += i) primes[j] = i;
    }
  for (int i = (2); i <= (M - 5); i++)
    if (primes[i] == 0) primes[i] = i;
}
int _mobius(int X) {
  int ret = 1;
  while (X > 1) {
    int u = primes[X];
    int cnt = 0;
    ret *= -1;
    while (X % u == 0) {
      X /= u;
      cnt++;
    }
    if (cnt >= 2) return 0;
  }
  return ret;
}
vector<int> divi[N], multi[N], a;
int n;
void prep() {
  eratosthene();
  for (int i = (1); i <= (N - 5); i++) mobius[i] = _mobius(i);
  for (int i = (1); i <= (N - 5); i++) {
    for (int j = i; j <= N - 5; j += i) divi[j].push_back(i);
  }
  for (auto &num : a) {
    for (auto &div : divi[num]) multi[div].push_back(num / div);
  }
  for (int i = (1); i <= (N - 5); i++) {
    vector<int> nx;
    for (auto &it : divi[i])
      if (mobius[it] != 0) nx.push_back(it);
    divi[i].swap(nx);
  }
}
int cnt[N];
void modify(int num, int dir) {
  for (auto &it : divi[num]) cnt[it] += dir;
}
ll countN(int num) {
  ll ret = 0;
  for (auto &it : divi[num]) {
    ret += mobius[it] * cnt[it];
  }
  return ret;
}
ll solve(int lab, vector<int> &inp) {
  ll ret = 0;
  stack<int> st;
  for (auto &it : inp) {
    int last = 0;
    while (!st.empty() && countN(it) != 0) {
      last = st.top();
      modify(last, -1);
      st.pop();
    }
    modify(it, 1);
    st.push(it);
    ret = max(ret, 1LL * it * last * lab);
  }
  while (!st.empty()) {
    int u = st.top();
    st.pop();
    modify(u, -1);
  }
  return ret;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll ans = 0;
  cin >> n;
  for (int i = (1); i <= (n); i++) {
    int t;
    cin >> t;
    a.push_back(t);
  }
  sort(a.begin(), a.end(), greater<int>());
  for (int i = (1); i <= (a.size() - 1); i++)
    if (a[i] == a[i - 1]) {
      ans = a[i];
      break;
    }
  a.resize(distance(a.begin(), unique(a.begin(), a.end())));
  prep();
  for (int i = (1); i <= (N - 5); i++) {
    ans = max(ans, solve(i, multi[i]));
  }
  cout << ans << '\n';
}

```