#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int mark[N], L[N], R[N], num[N], cnt[N];
vector<int> P[N], qry[N];
void add(int x) {
  for (int msk = 0; msk < (1 << (int)(P[x].size())); msk++) {
    if (msk)
      num[msk] =
          num[msk ^ (1 << __builtin_ctz(msk))] * P[x][__builtin_ctz(msk)];
    cnt[num[msk]]++;
  }
}
bool ok(int x) {
  int res = 0;
  for (int msk = 0; msk < (1 << (int)(P[x].size())); msk++) {
    if (msk)
      num[msk] =
          num[msk ^ (1 << __builtin_ctz(msk))] * P[x][__builtin_ctz(msk)];
    res += (__builtin_popcount(msk) & 1 ? -1 : 1) * cnt[num[msk]];
  }
  return 0 < res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, x;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x, mark[x] = 1;
  n = 100000;
  for (int i = 1; i <= n; i++) {
    if (mark[i]) continue;
    for (int j = i; j <= n; j += i) {
      if (mark[j]) {
        mark[i] = 1;
        break;
      }
    }
  }
  for (int i = 2; i <= n; i++)
    if (P[i].empty())
      for (int j = i; j <= n; j += i) P[j].push_back(i);
  num[0] = 1;
  for (int i = 1; i <= n; i++)
    if (mark[i]) L[i] = 1, R[i] = n + 1;
  for (int _ = 0; _ < 20; _++) {
    for (int i = 1; i <= n; i++)
      if (1 < R[i] - L[i]) qry[(L[i] + R[i]) >> 1].push_back(i);
    for (int i = n; i; i--) {
      if (mark[i]) add(i);
      for (int j : qry[i]) {
        if (ok(j))
          L[j] = (L[j] + R[j]) >> 1;
        else
          R[j] = (L[j] + R[j]) >> 1;
      }
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) qry[i].clear();
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) ans = max(ans, 1LL * i * L[i]);
  cout << ans;
  return 0;
}

### Prompt

Generate 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 int N = 1e5 + 5;
int mark[N], L[N], R[N], num[N], cnt[N];
vector<int> P[N], qry[N];
void add(int x) {
  for (int msk = 0; msk < (1 << (int)(P[x].size())); msk++) {
    if (msk)
      num[msk] =
          num[msk ^ (1 << __builtin_ctz(msk))] * P[x][__builtin_ctz(msk)];
    cnt[num[msk]]++;
  }
}
bool ok(int x) {
  int res = 0;
  for (int msk = 0; msk < (1 << (int)(P[x].size())); msk++) {
    if (msk)
      num[msk] =
          num[msk ^ (1 << __builtin_ctz(msk))] * P[x][__builtin_ctz(msk)];
    res += (__builtin_popcount(msk) & 1 ? -1 : 1) * cnt[num[msk]];
  }
  return 0 < res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, x;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x, mark[x] = 1;
  n = 100000;
  for (int i = 1; i <= n; i++) {
    if (mark[i]) continue;
    for (int j = i; j <= n; j += i) {
      if (mark[j]) {
        mark[i] = 1;
        break;
      }
    }
  }
  for (int i = 2; i <= n; i++)
    if (P[i].empty())
      for (int j = i; j <= n; j += i) P[j].push_back(i);
  num[0] = 1;
  for (int i = 1; i <= n; i++)
    if (mark[i]) L[i] = 1, R[i] = n + 1;
  for (int _ = 0; _ < 20; _++) {
    for (int i = 1; i <= n; i++)
      if (1 < R[i] - L[i]) qry[(L[i] + R[i]) >> 1].push_back(i);
    for (int i = n; i; i--) {
      if (mark[i]) add(i);
      for (int j : qry[i]) {
        if (ok(j))
          L[j] = (L[j] + R[j]) >> 1;
        else
          R[j] = (L[j] + R[j]) >> 1;
      }
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) qry[i].clear();
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) ans = max(ans, 1LL * i * L[i]);
  cout << ans;
  return 0;
}

```