#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
pair<vector<int>, vector<int>> sieve(int n) {
  vector<int> primes;
  vector<int> div_ind(n + 1, -1);
  for (int i = 2; i <= n; ++i) {
    if (div_ind[i] == -1) {
      div_ind[i] = primes.size();
      primes.push_back(i);
    }
    for (int j = 0; j <= div_ind[i]; ++j) {
      int t = primes[j] * i;
      if (t > n) break;
      div_ind[t] = j;
    }
  }
  return {primes, div_ind};
}
int bins(const vector<int>& vec, int v) {
  int low = 0;
  int high = (int)vec.size();
  while (low != high) {
    int mid = (low + high) >> 1;
    if (vec[mid] <= v)
      low = mid + 1;
    else
      high = mid;
  }
  return low;
}
int search(const vector<int>& pos, const vector<int>& neg,
           const vector<vector<int>>& ord) {
  int i = pos[0];
  int low = 0;
  int high = (int)ord[i].size() - 1;
  while (low != high) {
    int mid = (low + high) >> 1;
    int v = ord[i][mid];
    int cou = 0;
    for (auto j : pos) cou += bins(ord[j], v);
    for (auto j : neg) cou -= bins(ord[j], v);
    if (cou > 0)
      high = mid;
    else
      low = mid + 1;
  }
  return ord[i][low];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int act;
  cin >> act;
  vector<int> vals(act);
  int n = 1;
  for (int& v : vals) {
    cin >> v;
    n = max(n, v);
  }
  vector<int> cou(n + 1, 0);
  for (auto v : vals) ++cou[v];
  for (int i = 1; i <= n; ++i) {
    for (int j = 2; i * j <= n; ++j) cou[i] += cou[i * j];
  }
  vector<int> primes, div_ind;
  tie(primes, div_ind) = sieve(n);
  vector<vector<int>> ord(n + 1);
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; k * i <= n; ++i) {
      if (cou[k * i]) ord[k].push_back(-k * i);
    }
    reverse(ord[k].begin(), ord[k].end());
  }
  ll res1 = 1;
  for (int k = 1; k <= n; ++k) {
    if (!cou[k]) continue;
    vector<int> ps;
    for (int x = k; x > 1;) {
      int j = div_ind[x];
      while (div_ind[x] == j) x /= primes[j];
      ps.push_back(primes[j]);
    }
    int cou = ps.size();
    vector<int> pos, neg;
    for (int m = 0; m < (1 << cou); ++m) {
      int ind = 1;
      for (int j = 0; j < cou; ++j) {
        if (m & (1 << j)) ind *= ps[j];
      }
      if (__builtin_parity(m))
        neg.push_back(ind);
      else
        pos.push_back(ind);
    }
    ll t = -search(pos, neg, ord);
    res1 = max(res1, k * t);
  }
  int res0 = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; i * j <= n; ++j) {
      if (gcd(i, j) == 1 && cou[i] && cou[j] &&
          (cou[i] > 1 || cou[j] > 1 || cou[i * j] != 1))
        res0 = max(res0, i * j);
    }
  }
  if (res1 <= n)
    cout << res0 << '\n';
  else
    cout << res1 << '\n';
}

### Prompt

Please create a solution in CPP 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;
using ll = long long;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
pair<vector<int>, vector<int>> sieve(int n) {
  vector<int> primes;
  vector<int> div_ind(n + 1, -1);
  for (int i = 2; i <= n; ++i) {
    if (div_ind[i] == -1) {
      div_ind[i] = primes.size();
      primes.push_back(i);
    }
    for (int j = 0; j <= div_ind[i]; ++j) {
      int t = primes[j] * i;
      if (t > n) break;
      div_ind[t] = j;
    }
  }
  return {primes, div_ind};
}
int bins(const vector<int>& vec, int v) {
  int low = 0;
  int high = (int)vec.size();
  while (low != high) {
    int mid = (low + high) >> 1;
    if (vec[mid] <= v)
      low = mid + 1;
    else
      high = mid;
  }
  return low;
}
int search(const vector<int>& pos, const vector<int>& neg,
           const vector<vector<int>>& ord) {
  int i = pos[0];
  int low = 0;
  int high = (int)ord[i].size() - 1;
  while (low != high) {
    int mid = (low + high) >> 1;
    int v = ord[i][mid];
    int cou = 0;
    for (auto j : pos) cou += bins(ord[j], v);
    for (auto j : neg) cou -= bins(ord[j], v);
    if (cou > 0)
      high = mid;
    else
      low = mid + 1;
  }
  return ord[i][low];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int act;
  cin >> act;
  vector<int> vals(act);
  int n = 1;
  for (int& v : vals) {
    cin >> v;
    n = max(n, v);
  }
  vector<int> cou(n + 1, 0);
  for (auto v : vals) ++cou[v];
  for (int i = 1; i <= n; ++i) {
    for (int j = 2; i * j <= n; ++j) cou[i] += cou[i * j];
  }
  vector<int> primes, div_ind;
  tie(primes, div_ind) = sieve(n);
  vector<vector<int>> ord(n + 1);
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; k * i <= n; ++i) {
      if (cou[k * i]) ord[k].push_back(-k * i);
    }
    reverse(ord[k].begin(), ord[k].end());
  }
  ll res1 = 1;
  for (int k = 1; k <= n; ++k) {
    if (!cou[k]) continue;
    vector<int> ps;
    for (int x = k; x > 1;) {
      int j = div_ind[x];
      while (div_ind[x] == j) x /= primes[j];
      ps.push_back(primes[j]);
    }
    int cou = ps.size();
    vector<int> pos, neg;
    for (int m = 0; m < (1 << cou); ++m) {
      int ind = 1;
      for (int j = 0; j < cou; ++j) {
        if (m & (1 << j)) ind *= ps[j];
      }
      if (__builtin_parity(m))
        neg.push_back(ind);
      else
        pos.push_back(ind);
    }
    ll t = -search(pos, neg, ord);
    res1 = max(res1, k * t);
  }
  int res0 = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; i * j <= n; ++j) {
      if (gcd(i, j) == 1 && cou[i] && cou[j] &&
          (cou[i] > 1 || cou[j] > 1 || cou[i * j] != 1))
        res0 = max(res0, i * j);
    }
  }
  if (res1 <= n)
    cout << res0 << '\n';
  else
    cout << res1 << '\n';
}

```