#include <bits/stdc++.h>
#pragma GCC optimize("O3")
const double PI = acos(-1);
template <class A, class B>
std::ostream& operator<<(std::ostream& st, const std::pair<A, B> p) {
  st << "(" << p.first << ", " << p.second << ")";
  return st;
}
using namespace std;
const int MAXA = 100 * 1000 + 1;
int prime[MAXA];
std::vector<int> primes[MAXA];
int prime_cnt[MAXA];
int canon[MAXA];
void sieve() {
  canon[1] = 1;
  for (int i = 2; i < MAXA; i++) {
    if (!prime[i]) {
      prime[i] = i;
      for (long long j = i * (long long)i; j < MAXA; j += i) prime[j] = i;
    }
    int p = prime[i];
    int n = i, e = 0;
    while (n % p == 0) n /= p, e++;
    prime_cnt[i] = prime_cnt[n] + 1;
    for (int q : primes[n]) primes[i].push_back(q);
    primes[i].push_back(p);
    sort(primes[i].begin(), primes[i].end());
    canon[i] = canon[n] * p;
  }
}
int cnt[MAXA];
int A[1 << 20], n;
bool bad[MAXA];
bool taken[MAXA];
int f[MAXA];
void update(int x, int v) {
  const std::vector<int>& P = primes[x];
  int m = ((int)P.size());
  for (int msk = 0; msk < (1 << m); msk++) {
    int g = 1;
    for (int i = 0; i < m; i++)
      if (msk & (1 << i)) g *= P[i];
    f[g] += v;
  }
}
int get(int x) {
  const std::vector<int>& P = primes[x];
  int m = ((int)P.size());
  int ret = 0;
  for (int msk = 0; msk < (1 << m); msk++) {
    int g = 1, sgn = 1;
    for (int i = 0; i < m; i++)
      if (msk & (1 << i)) g *= P[i], sgn *= -1;
    ret += sgn * f[g];
  }
  return ret;
}
int main() {
  sieve();
  scanf("%d", &n);
  for (int i = 0; i < (n); i++) {
    scanf("%d", A + i);
    cnt[A[i]]++;
  }
  long long ans = -1;
  sort(A, A + n);
  n = unique(A, A + n) - A;
  std::pair<int, int> mx(0, 0), mx2(0, 0);
  for (int k = 0; k < (n); k++) {
    int x = A[k];
    if (cnt[x] > 1) ans = max(ans, x + 0LL);
  }
  std::vector<int> V;
  std::vector<int> best;
  for (int g = 1; g < MAXA; g++) {
    V.clear();
    for (int i = MAXA - MAXA % g; i >= g; i -= g) {
      if (i >= MAXA) continue;
      int x = i / g;
      if (cnt[i] && !taken[x]) {
        V.push_back(x);
        taken[canon[x]] = 1;
      }
    }
    for (int i = MAXA - MAXA % g; i >= g; i -= g) {
      if (i >= MAXA) continue;
      taken[canon[i / g]] = 0;
    }
    if (((int)V.size()) <= 1) continue;
    long long ret = 0;
    for (int v : V) {
      int lst = 0;
      while (get(v) > 0) {
        int u = best.back();
        lst = u;
        best.pop_back();
        update(u, -1);
      }
      if (lst) {
        best.push_back(lst);
        update(lst, 1);
      }
      best.push_back(v);
      update(v, 1);
      ret = max(ret, v * (long long)lst);
    }
    while (!best.empty()) {
      update(best.back(), -1);
      best.pop_back();
    }
    ans = max(ans, g * ret);
  }
  cout << ans << endl;
  return 0;
}

### 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>
#pragma GCC optimize("O3")
const double PI = acos(-1);
template <class A, class B>
std::ostream& operator<<(std::ostream& st, const std::pair<A, B> p) {
  st << "(" << p.first << ", " << p.second << ")";
  return st;
}
using namespace std;
const int MAXA = 100 * 1000 + 1;
int prime[MAXA];
std::vector<int> primes[MAXA];
int prime_cnt[MAXA];
int canon[MAXA];
void sieve() {
  canon[1] = 1;
  for (int i = 2; i < MAXA; i++) {
    if (!prime[i]) {
      prime[i] = i;
      for (long long j = i * (long long)i; j < MAXA; j += i) prime[j] = i;
    }
    int p = prime[i];
    int n = i, e = 0;
    while (n % p == 0) n /= p, e++;
    prime_cnt[i] = prime_cnt[n] + 1;
    for (int q : primes[n]) primes[i].push_back(q);
    primes[i].push_back(p);
    sort(primes[i].begin(), primes[i].end());
    canon[i] = canon[n] * p;
  }
}
int cnt[MAXA];
int A[1 << 20], n;
bool bad[MAXA];
bool taken[MAXA];
int f[MAXA];
void update(int x, int v) {
  const std::vector<int>& P = primes[x];
  int m = ((int)P.size());
  for (int msk = 0; msk < (1 << m); msk++) {
    int g = 1;
    for (int i = 0; i < m; i++)
      if (msk & (1 << i)) g *= P[i];
    f[g] += v;
  }
}
int get(int x) {
  const std::vector<int>& P = primes[x];
  int m = ((int)P.size());
  int ret = 0;
  for (int msk = 0; msk < (1 << m); msk++) {
    int g = 1, sgn = 1;
    for (int i = 0; i < m; i++)
      if (msk & (1 << i)) g *= P[i], sgn *= -1;
    ret += sgn * f[g];
  }
  return ret;
}
int main() {
  sieve();
  scanf("%d", &n);
  for (int i = 0; i < (n); i++) {
    scanf("%d", A + i);
    cnt[A[i]]++;
  }
  long long ans = -1;
  sort(A, A + n);
  n = unique(A, A + n) - A;
  std::pair<int, int> mx(0, 0), mx2(0, 0);
  for (int k = 0; k < (n); k++) {
    int x = A[k];
    if (cnt[x] > 1) ans = max(ans, x + 0LL);
  }
  std::vector<int> V;
  std::vector<int> best;
  for (int g = 1; g < MAXA; g++) {
    V.clear();
    for (int i = MAXA - MAXA % g; i >= g; i -= g) {
      if (i >= MAXA) continue;
      int x = i / g;
      if (cnt[i] && !taken[x]) {
        V.push_back(x);
        taken[canon[x]] = 1;
      }
    }
    for (int i = MAXA - MAXA % g; i >= g; i -= g) {
      if (i >= MAXA) continue;
      taken[canon[i / g]] = 0;
    }
    if (((int)V.size()) <= 1) continue;
    long long ret = 0;
    for (int v : V) {
      int lst = 0;
      while (get(v) > 0) {
        int u = best.back();
        lst = u;
        best.pop_back();
        update(u, -1);
      }
      if (lst) {
        best.push_back(lst);
        update(lst, 1);
      }
      best.push_back(v);
      update(v, 1);
      ret = max(ret, v * (long long)lst);
    }
    while (!best.empty()) {
      update(best.back(), -1);
      best.pop_back();
    }
    ans = max(ans, g * ret);
  }
  cout << ans << endl;
  return 0;
}

```