#include <bits/stdc++.h>
using namespace std;
long long x, n, N, a[100005], dau, L[100005], R[100005], cao[100005], m[100005],
    kq[100005], KQ, mid, sntcn[100005], tich, sl, v[100005];
vector<int> nt;
vector<pair<int, int> > tt[100005];
vector<int> vec[100005];
bool check[100005];
void dq(int i, int sl, int tich, int so) {
  if (i == nt.size()) {
    tt[so].push_back({tich, sl & 1});
    return;
  }
  for (int j = 0; j < 2; ++j) {
    if (j == 1) tich *= nt[i];
    dq(i + 1, sl + j, tich, so);
  }
}
long long tinh() {
  for (int i = 1; i <= n; ++i) {
    L[i] = 1;
    R[i] = i - 1;
    kq[i] = 0;
    if (!tt[v[i]].empty()) continue;
    x = v[i];
    nt.clear();
    while (x > 1) {
      if (nt.empty() || nt.back() != m[x]) nt.push_back(m[x]);
      x /= m[x];
    }
    dq(0, 0, 1, v[i]);
  }
  while (L[n] <= R[n]) {
    for (int i = 1; i <= n; ++i) {
      mid = (R[i] + L[i]) / 2;
      sntcn[i] = 0;
      for (int j = 0; j < tt[v[i]].size(); ++j) cao[tt[v[i]][j].first] = 0;
      if (L[i] <= R[i]) vec[mid].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
      int t = 0;
      for (int j = 0; j < tt[v[i]].size(); ++j) {
        if (tt[v[i]][j].second == 0)
          t += cao[tt[v[i]][j].first];
        else
          t -= cao[tt[v[i]][j].first];
      }
      while (!vec[i].empty()) {
        int vt = vec[i].back();
        vec[i].pop_back();
        for (int j = 0; j < tt[v[vt]].size(); j++) {
          if (tt[v[vt]][j].second == 0)
            sntcn[vt] += cao[tt[v[vt]][j].first];
          else
            sntcn[vt] -= cao[tt[v[vt]][j].first];
        }
      }
      sntcn[i] = t - sntcn[i];
      for (int j = 0; j < tt[v[i]].size(); ++j) cao[tt[v[i]][j].first]++;
    }
    for (int i = 1; i <= n; ++i) {
      if (L[i] > R[i]) continue;
      mid = (R[i] + L[i]) / 2;
      if (sntcn[i] > 0) {
        kq[i] = mid;
        L[i] = mid + 1;
      } else
        R[i] = mid - 1;
    }
  }
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    res = max(res, v[i] * v[kq[i]]);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i * i <= 100000; ++i)
    if (m[i] == 0)
      for (int j = i * i; j <= 100000; j += i)
        if (m[j] == 0) m[j] = i;
  for (int i = 2; i <= 100000; ++i)
    if (m[i] == 0) m[i] = i;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    check[a[i]] = true;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i)
    if (a[i] == a[i - 1]) KQ = max(KQ, a[i]);
  for (int i = 1; i <= 100000; ++i) {
    n = 0;
    for (int j = i; j <= 100000; j += i)
      if (check[j]) v[++n] = j / i;
    if (n < 2) continue;
    KQ = max(KQ, tinh() * i);
  }
  cout << KQ;
  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;
long long x, n, N, a[100005], dau, L[100005], R[100005], cao[100005], m[100005],
    kq[100005], KQ, mid, sntcn[100005], tich, sl, v[100005];
vector<int> nt;
vector<pair<int, int> > tt[100005];
vector<int> vec[100005];
bool check[100005];
void dq(int i, int sl, int tich, int so) {
  if (i == nt.size()) {
    tt[so].push_back({tich, sl & 1});
    return;
  }
  for (int j = 0; j < 2; ++j) {
    if (j == 1) tich *= nt[i];
    dq(i + 1, sl + j, tich, so);
  }
}
long long tinh() {
  for (int i = 1; i <= n; ++i) {
    L[i] = 1;
    R[i] = i - 1;
    kq[i] = 0;
    if (!tt[v[i]].empty()) continue;
    x = v[i];
    nt.clear();
    while (x > 1) {
      if (nt.empty() || nt.back() != m[x]) nt.push_back(m[x]);
      x /= m[x];
    }
    dq(0, 0, 1, v[i]);
  }
  while (L[n] <= R[n]) {
    for (int i = 1; i <= n; ++i) {
      mid = (R[i] + L[i]) / 2;
      sntcn[i] = 0;
      for (int j = 0; j < tt[v[i]].size(); ++j) cao[tt[v[i]][j].first] = 0;
      if (L[i] <= R[i]) vec[mid].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
      int t = 0;
      for (int j = 0; j < tt[v[i]].size(); ++j) {
        if (tt[v[i]][j].second == 0)
          t += cao[tt[v[i]][j].first];
        else
          t -= cao[tt[v[i]][j].first];
      }
      while (!vec[i].empty()) {
        int vt = vec[i].back();
        vec[i].pop_back();
        for (int j = 0; j < tt[v[vt]].size(); j++) {
          if (tt[v[vt]][j].second == 0)
            sntcn[vt] += cao[tt[v[vt]][j].first];
          else
            sntcn[vt] -= cao[tt[v[vt]][j].first];
        }
      }
      sntcn[i] = t - sntcn[i];
      for (int j = 0; j < tt[v[i]].size(); ++j) cao[tt[v[i]][j].first]++;
    }
    for (int i = 1; i <= n; ++i) {
      if (L[i] > R[i]) continue;
      mid = (R[i] + L[i]) / 2;
      if (sntcn[i] > 0) {
        kq[i] = mid;
        L[i] = mid + 1;
      } else
        R[i] = mid - 1;
    }
  }
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    res = max(res, v[i] * v[kq[i]]);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i * i <= 100000; ++i)
    if (m[i] == 0)
      for (int j = i * i; j <= 100000; j += i)
        if (m[j] == 0) m[j] = i;
  for (int i = 2; i <= 100000; ++i)
    if (m[i] == 0) m[i] = i;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    check[a[i]] = true;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i)
    if (a[i] == a[i - 1]) KQ = max(KQ, a[i]);
  for (int i = 1; i <= 100000; ++i) {
    n = 0;
    for (int j = i; j <= 100000; j += i)
      if (check[j]) v[++n] = j / i;
    if (n < 2) continue;
    KQ = max(KQ, tinh() * i);
  }
  cout << KQ;
  return 0;
}

```