#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
bool h[N];
vector<long long> fac[N];
long long sfd[N];
long long cnt[N];
bool coprime(long long idx) {
  long long ans = 0;
  for (auto i : fac[idx]) ans += cnt[i] * sfd[i];
  return ans;
}
void update(long long idx, long long x) {
  for (auto i : fac[idx]) cnt[i] += x;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  {
    long long n;
    cin >> n;
    long long a[n], mx = 0;
    for (long long i = 0; i < n; i++) {
      cin >> a[i];
      h[a[i]] = 1;
      mx = max(mx, a[i]);
    }
    for (long long i = 1; i < N; i++) {
      for (long long j = i; j < N; j += i) fac[j].push_back(i);
      if (i == 1)
        sfd[i] = 1;
      else if ((i / fac[i][1]) % fac[i][1] == 0)
        sfd[i] = 0;
      else
        sfd[i] = -sfd[i / fac[i][1]];
    }
    for (long long i = 1; i < N; i++) {
      for (long long j = 1; i * j < N; j++) h[i] = h[i] || h[i * j];
    }
    vector<long long> v;
    for (long long i = N - 2; i > 0; i--) {
      if (h[i]) {
        while (coprime(i)) {
          mx = max(mx, i * v.back());
          update(v.back(), -1);
          v.pop_back();
        }
        update(i, 1);
        v.push_back(i);
      }
    }
    cout << mx << '\n';
  }
  cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \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;
const long long N = 1e5 + 5;
bool h[N];
vector<long long> fac[N];
long long sfd[N];
long long cnt[N];
bool coprime(long long idx) {
  long long ans = 0;
  for (auto i : fac[idx]) ans += cnt[i] * sfd[i];
  return ans;
}
void update(long long idx, long long x) {
  for (auto i : fac[idx]) cnt[i] += x;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  {
    long long n;
    cin >> n;
    long long a[n], mx = 0;
    for (long long i = 0; i < n; i++) {
      cin >> a[i];
      h[a[i]] = 1;
      mx = max(mx, a[i]);
    }
    for (long long i = 1; i < N; i++) {
      for (long long j = i; j < N; j += i) fac[j].push_back(i);
      if (i == 1)
        sfd[i] = 1;
      else if ((i / fac[i][1]) % fac[i][1] == 0)
        sfd[i] = 0;
      else
        sfd[i] = -sfd[i / fac[i][1]];
    }
    for (long long i = 1; i < N; i++) {
      for (long long j = 1; i * j < N; j++) h[i] = h[i] || h[i * j];
    }
    vector<long long> v;
    for (long long i = N - 2; i > 0; i--) {
      if (h[i]) {
        while (coprime(i)) {
          mx = max(mx, i * v.back());
          update(v.back(), -1);
          v.pop_back();
        }
        update(i, 1);
        v.push_back(i);
      }
    }
    cout << mx << '\n';
  }
  cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
  return 0;
}

```