#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n;
int a[MAXN];
int sum[MAXN];
int mid[MAXN];
int pinkgermany[MAXN];
int germanypink[MAXN];
int risan[MAXN];
long long ans;
int log2_[MAXN];
int query_size[MAXN];
int mask_count[MAXN];
vector<int> prime_factor[MAXN];
vector<pair<int, int> > queries[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 2; i < MAXN; ++i) {
    if (prime_factor[i].size()) continue;
    for (int j = i; j < MAXN; j += i) prime_factor[j].push_back(i);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    long long x;
    cin >> x;
    a[x] = 1;
    ans = max(ans, x);
  }
  for (int i = 2; i < MAXN; ++i) {
    log2_[i] = log2_[i >> 1] + 1;
  }
  for (int g = 1; g < MAXN; g++) {
    vector<int> b;
    b.reserve(MAXN / g + 1);
    for (int x = g; x < MAXN; x += g) {
      if (a[x]) b.push_back(x / g);
    }
    if (b.size() == 0) continue;
    for (int i = 1; i < b.size(); ++i) {
      risan[i] = -1;
      pinkgermany[i] = 0;
      germanypink[i] = i - 1;
      if (b[i - 1] + 1 == b[i]) {
        risan[i] = i - 1;
        pinkgermany[i] = i;
      }
    }
    int max_log = log2_[b.size()] + 1;
    for (int log_ = 0; log_ < max_log; ++log_) {
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        mid[i] = (pinkgermany[i] + germanypink[i]) >> 1;
        ++query_size[i - 1];
        if (mid[i] > 0) ++query_size[mid[i] - 1];
      }
      for (int i = 0; i < b.size(); ++i) queries[i].reserve(query_size[i] + 1);
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        queries[i - 1].push_back({i, b[i]});
        if (mid[i] > 0) queries[mid[i] - 1].push_back({-i, b[i]});
      }
      for (int i = 0; i < b.size(); ++i) {
        for (int mask = 0; mask < (1 << prime_factor[b[i]].size()); ++mask) {
          int prod = 1;
          for (int j = 0; j < prime_factor[b[i]].size(); ++j) {
            if (mask & (1 << j)) prod *= prime_factor[b[i]][j];
          }
          ++mask_count[prod];
        }
        for (auto &q : queries[i]) {
          int id = abs(q.first), sign = id / q.first, val = q.second;
          for (int mask = 0; mask < (1 << prime_factor[val].size()); ++mask) {
            int prod = 1;
            for (int j = 0; j < prime_factor[val].size(); ++j) {
              if (mask & (1 << j)) prod *= prime_factor[val][j];
            }
            int sign2 = __builtin_popcount(mask) % 2 ? -1 : 1;
            sum[id] += sign * sign2 * mask_count[prod];
          }
        }
      }
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        if (sum[i]) {
          risan[i] = mid[i];
          pinkgermany[i] = mid[i] + 1;
        } else
          germanypink[i] = mid[i] - 1;
      }
      for (int i = 0; i < b.size(); ++i) {
        queries[i].clear();
        query_size[i] = 0;
        sum[i] = 0;
        for (int mask = 0; mask < (1 << prime_factor[b[i]].size()); ++mask) {
          int prod = 1;
          for (int j = 0; j < prime_factor[b[i]].size(); ++j) {
            if (mask & (1 << j)) prod *= prime_factor[b[i]][j];
          }
          mask_count[prod] = 0;
        }
      }
    }
    for (int i = 1; i < b.size(); ++i) {
      if (risan[i] >= 0) ans = max(ans, 1LL * b[i] * b[risan[i]] * g);
    }
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

Your task is to create 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 MAXN = 100010;
int n;
int a[MAXN];
int sum[MAXN];
int mid[MAXN];
int pinkgermany[MAXN];
int germanypink[MAXN];
int risan[MAXN];
long long ans;
int log2_[MAXN];
int query_size[MAXN];
int mask_count[MAXN];
vector<int> prime_factor[MAXN];
vector<pair<int, int> > queries[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 2; i < MAXN; ++i) {
    if (prime_factor[i].size()) continue;
    for (int j = i; j < MAXN; j += i) prime_factor[j].push_back(i);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    long long x;
    cin >> x;
    a[x] = 1;
    ans = max(ans, x);
  }
  for (int i = 2; i < MAXN; ++i) {
    log2_[i] = log2_[i >> 1] + 1;
  }
  for (int g = 1; g < MAXN; g++) {
    vector<int> b;
    b.reserve(MAXN / g + 1);
    for (int x = g; x < MAXN; x += g) {
      if (a[x]) b.push_back(x / g);
    }
    if (b.size() == 0) continue;
    for (int i = 1; i < b.size(); ++i) {
      risan[i] = -1;
      pinkgermany[i] = 0;
      germanypink[i] = i - 1;
      if (b[i - 1] + 1 == b[i]) {
        risan[i] = i - 1;
        pinkgermany[i] = i;
      }
    }
    int max_log = log2_[b.size()] + 1;
    for (int log_ = 0; log_ < max_log; ++log_) {
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        mid[i] = (pinkgermany[i] + germanypink[i]) >> 1;
        ++query_size[i - 1];
        if (mid[i] > 0) ++query_size[mid[i] - 1];
      }
      for (int i = 0; i < b.size(); ++i) queries[i].reserve(query_size[i] + 1);
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        queries[i - 1].push_back({i, b[i]});
        if (mid[i] > 0) queries[mid[i] - 1].push_back({-i, b[i]});
      }
      for (int i = 0; i < b.size(); ++i) {
        for (int mask = 0; mask < (1 << prime_factor[b[i]].size()); ++mask) {
          int prod = 1;
          for (int j = 0; j < prime_factor[b[i]].size(); ++j) {
            if (mask & (1 << j)) prod *= prime_factor[b[i]][j];
          }
          ++mask_count[prod];
        }
        for (auto &q : queries[i]) {
          int id = abs(q.first), sign = id / q.first, val = q.second;
          for (int mask = 0; mask < (1 << prime_factor[val].size()); ++mask) {
            int prod = 1;
            for (int j = 0; j < prime_factor[val].size(); ++j) {
              if (mask & (1 << j)) prod *= prime_factor[val][j];
            }
            int sign2 = __builtin_popcount(mask) % 2 ? -1 : 1;
            sum[id] += sign * sign2 * mask_count[prod];
          }
        }
      }
      for (int i = 1; i < b.size(); ++i) {
        if (pinkgermany[i] > germanypink[i]) continue;
        if (sum[i]) {
          risan[i] = mid[i];
          pinkgermany[i] = mid[i] + 1;
        } else
          germanypink[i] = mid[i] - 1;
      }
      for (int i = 0; i < b.size(); ++i) {
        queries[i].clear();
        query_size[i] = 0;
        sum[i] = 0;
        for (int mask = 0; mask < (1 << prime_factor[b[i]].size()); ++mask) {
          int prod = 1;
          for (int j = 0; j < prime_factor[b[i]].size(); ++j) {
            if (mask & (1 << j)) prod *= prime_factor[b[i]][j];
          }
          mask_count[prod] = 0;
        }
      }
    }
    for (int i = 1; i < b.size(); ++i) {
      if (risan[i] >= 0) ans = max(ans, 1LL * b[i] * b[risan[i]] * g);
    }
  }
  cout << ans << "\n";
  return 0;
}

```