#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  sort(a.begin(), a.end());
  long long ans = 0;
  for (int i = 1; i < n; ++i)
    if (a[i] == a[i - 1]) ans = max(ans, (long long)a[i]);
  a.erase(unique(a.begin(), a.end()), a.end());
  n = a.size();
  int mx = a.back();
  vector<vector<int>> divs(mx + 1);
  for (int i = 1; i <= mx; ++i)
    for (int j = i; j <= mx; j += i) divs[j].push_back(i);
  vector<int> mu(mx + 1, 1);
  for (int i = 1; i <= mx; ++i)
    for (int j = i; j > 1;) {
      int p = divs[j][1];
      j /= p;
      mu[i] = -mu[i];
      if (j % p == 0) {
        mu[i] = 0;
        break;
      }
    }
  vector<int> stk, cnt(mx + 1);
  reverse(a.begin(), a.end());
  auto add = [&](int x, int y) {
    if (y == -1)
      stk.pop_back();
    else
      stk.push_back(x);
    for (auto i : divs[x]) cnt[i] += y;
  };
  vector<vector<int>> mp(mx + 1);
  for (auto i : a)
    for (auto j : divs[i]) mp[j].push_back(i / j);
  for (int g = 1; g <= mx; ++g) {
    for (auto i : mp[g]) {
      for (int j = 0;;) {
        int x = 0;
        for (auto j : divs[i]) x += mu[j] * cnt[j];
        if (x > 0)
          j = stk.back(), add(j, -1);
        else {
          ans = max(ans, (long long)i * j * g);
          break;
        }
      }
      add(i, +1);
    }
    while (!stk.empty()) add(stk.back(), -1);
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

Your challenge is to write 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 main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  sort(a.begin(), a.end());
  long long ans = 0;
  for (int i = 1; i < n; ++i)
    if (a[i] == a[i - 1]) ans = max(ans, (long long)a[i]);
  a.erase(unique(a.begin(), a.end()), a.end());
  n = a.size();
  int mx = a.back();
  vector<vector<int>> divs(mx + 1);
  for (int i = 1; i <= mx; ++i)
    for (int j = i; j <= mx; j += i) divs[j].push_back(i);
  vector<int> mu(mx + 1, 1);
  for (int i = 1; i <= mx; ++i)
    for (int j = i; j > 1;) {
      int p = divs[j][1];
      j /= p;
      mu[i] = -mu[i];
      if (j % p == 0) {
        mu[i] = 0;
        break;
      }
    }
  vector<int> stk, cnt(mx + 1);
  reverse(a.begin(), a.end());
  auto add = [&](int x, int y) {
    if (y == -1)
      stk.pop_back();
    else
      stk.push_back(x);
    for (auto i : divs[x]) cnt[i] += y;
  };
  vector<vector<int>> mp(mx + 1);
  for (auto i : a)
    for (auto j : divs[i]) mp[j].push_back(i / j);
  for (int g = 1; g <= mx; ++g) {
    for (auto i : mp[g]) {
      for (int j = 0;;) {
        int x = 0;
        for (auto j : divs[i]) x += mu[j] * cnt[j];
        if (x > 0)
          j = stk.back(), add(j, -1);
        else {
          ans = max(ans, (long long)i * j * g);
          break;
        }
      }
      add(i, +1);
    }
    while (!stk.empty()) add(stk.back(), -1);
  }
  cout << ans << "\n";
  return 0;
}

```