#include <bits/stdc++.h>
using namespace std;
template <typename T>
T getint() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * p;
}
template <typename T1, typename T2>
bool umin(T1 &x, const T2 &y) {
  if (x > y) return x = y, true;
  return false;
}
template <typename T1, typename T2>
bool umax(T1 &x, const T2 &y) {
  if (x < y) return x = y, true;
  return false;
}
const int maxn = (int)1e5 + 1;
const int inf = (int)1e9 + 5;
const int mod = (int)1e9 + 7;
const long long llinf = (long long)1e18 + 5;
const double pi = acos(-1.0);
int ok[maxn];
vector<int> d[maxn];
int c[maxn];
void add(int x, int delta) {
  for (int i : d[x]) {
    c[abs(i)] += delta;
  }
}
int get(int x) {
  int res = 0;
  for (int i : d[x]) {
    res += (i > 0 ? c[i] : -c[-i]);
  }
  return res;
}
long long solve(vector<int> values) {
  if (values.empty()) return 0;
  long long l = 0, r = values.back() * 1LL * values.back() + 1;
  while (r - l > 1) {
    long long md = (l + r) / 2;
    bool any = (md == 0 ? 1 : 0);
    int ptr = (int)values.size() - 1;
    for (int i = 0; i < values.size(); ++i) {
      int x = values[i];
      while (ptr >= 0 && values[ptr] * 1LL * x >= md && i < ptr) {
        add(values[ptr], +1);
        ptr--;
      }
      if (get(x) < (int)values.size() - ptr - 1) any = true;
    }
    if (any) {
      l = md;
    } else {
      r = md;
    }
    for (auto j = ptr + 1; j < values.size(); ++j) add(values[j], -1);
  }
  return l;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    ok[x]++;
  }
  for (int i = 1; i < maxn; ++i) {
    vector<int> primes;
    int x = i;
    for (int j = 2; j * j <= x; ++j) {
      if (x % j == 0) {
        primes.push_back(j);
        while (x % j == 0) x /= j;
      }
    }
    if (x > 1) primes.push_back(x);
    sort(primes.begin(), primes.end());
    int k = primes.size();
    for (int m = 1; m < (1 << k); ++m) {
      int pr = -1;
      for (int j = 0; j < k; ++j)
        if (m >> j & 1) {
          pr *= primes[j] * (-1);
        }
      d[i].push_back(pr);
    }
  }
  long long res = 1LL;
  for (int d = 1; d < maxn; ++d) {
    if (ok[d] >= 2) res = max(res, 1LL * d);
    vector<int> nums;
    for (int j = d; j < maxn; j += d) {
      if (ok[j] > 0) nums.push_back(j / d);
    }
    res = max(res, solve(nums) * d);
  }
  cout << res << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
template <typename T>
T getint() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * p;
}
template <typename T1, typename T2>
bool umin(T1 &x, const T2 &y) {
  if (x > y) return x = y, true;
  return false;
}
template <typename T1, typename T2>
bool umax(T1 &x, const T2 &y) {
  if (x < y) return x = y, true;
  return false;
}
const int maxn = (int)1e5 + 1;
const int inf = (int)1e9 + 5;
const int mod = (int)1e9 + 7;
const long long llinf = (long long)1e18 + 5;
const double pi = acos(-1.0);
int ok[maxn];
vector<int> d[maxn];
int c[maxn];
void add(int x, int delta) {
  for (int i : d[x]) {
    c[abs(i)] += delta;
  }
}
int get(int x) {
  int res = 0;
  for (int i : d[x]) {
    res += (i > 0 ? c[i] : -c[-i]);
  }
  return res;
}
long long solve(vector<int> values) {
  if (values.empty()) return 0;
  long long l = 0, r = values.back() * 1LL * values.back() + 1;
  while (r - l > 1) {
    long long md = (l + r) / 2;
    bool any = (md == 0 ? 1 : 0);
    int ptr = (int)values.size() - 1;
    for (int i = 0; i < values.size(); ++i) {
      int x = values[i];
      while (ptr >= 0 && values[ptr] * 1LL * x >= md && i < ptr) {
        add(values[ptr], +1);
        ptr--;
      }
      if (get(x) < (int)values.size() - ptr - 1) any = true;
    }
    if (any) {
      l = md;
    } else {
      r = md;
    }
    for (auto j = ptr + 1; j < values.size(); ++j) add(values[j], -1);
  }
  return l;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    ok[x]++;
  }
  for (int i = 1; i < maxn; ++i) {
    vector<int> primes;
    int x = i;
    for (int j = 2; j * j <= x; ++j) {
      if (x % j == 0) {
        primes.push_back(j);
        while (x % j == 0) x /= j;
      }
    }
    if (x > 1) primes.push_back(x);
    sort(primes.begin(), primes.end());
    int k = primes.size();
    for (int m = 1; m < (1 << k); ++m) {
      int pr = -1;
      for (int j = 0; j < k; ++j)
        if (m >> j & 1) {
          pr *= primes[j] * (-1);
        }
      d[i].push_back(pr);
    }
  }
  long long res = 1LL;
  for (int d = 1; d < maxn; ++d) {
    if (ok[d] >= 2) res = max(res, 1LL * d);
    vector<int> nums;
    for (int j = d; j < maxn; j += d) {
      if (ok[j] > 0) nums.push_back(j / d);
    }
    res = max(res, solve(nums) * d);
  }
  cout << res << endl;
  return 0;
}

```