#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, m, a[N + 9];
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    a[x] = 1;
    m = max(m, x);
  }
}
int mu[N + 9];
vector<int> d[N + 9];
void Get_mu() {
  mu[1] = 1;
  for (int i = 1; i <= m; ++i) {
    d[i].push_back(i);
    for (int j = i << 1; j <= m; j += i) {
      mu[j] -= mu[i];
      d[j].push_back(i);
    }
  }
}
int c[N + 9], cnt[N + 9];
long long Get_ans(int m) {
  long long res = 0;
  for (int i = 1; i <= m; ++i) {
    cnt[i] = 0;
    for (int j = i; j <= m; j += i) cnt[i] += c[j];
  }
  for (int i = m, j = 1; i >= j; --i) {
    if (!c[i]) continue;
    for (; j <= i; ++j) {
      int sum = 0;
      for (int x : d[i]) sum += mu[x] * cnt[x];
      if (!sum) break;
      res = max(res, 1LL * i * j);
      for (int x : d[j]) cnt[x] -= c[j];
    }
  }
  return res;
}
long long ans;
void Get_ans() {
  for (int i = m; i >= 1; --i) {
    for (int j = 1; i * j <= m; ++j) c[j] = a[i * j];
    ans = max(ans, Get_ans(m / i) * i);
  }
}
void work() {
  Get_mu();
  Get_ans();
}
void outo() { printf("%lld\n", ans); }
int main() {
  int T = 1;
  for (; T--;) {
    into();
    work();
    outo();
  }
  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 N = 100000;
int n, m, a[N + 9];
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    a[x] = 1;
    m = max(m, x);
  }
}
int mu[N + 9];
vector<int> d[N + 9];
void Get_mu() {
  mu[1] = 1;
  for (int i = 1; i <= m; ++i) {
    d[i].push_back(i);
    for (int j = i << 1; j <= m; j += i) {
      mu[j] -= mu[i];
      d[j].push_back(i);
    }
  }
}
int c[N + 9], cnt[N + 9];
long long Get_ans(int m) {
  long long res = 0;
  for (int i = 1; i <= m; ++i) {
    cnt[i] = 0;
    for (int j = i; j <= m; j += i) cnt[i] += c[j];
  }
  for (int i = m, j = 1; i >= j; --i) {
    if (!c[i]) continue;
    for (; j <= i; ++j) {
      int sum = 0;
      for (int x : d[i]) sum += mu[x] * cnt[x];
      if (!sum) break;
      res = max(res, 1LL * i * j);
      for (int x : d[j]) cnt[x] -= c[j];
    }
  }
  return res;
}
long long ans;
void Get_ans() {
  for (int i = m; i >= 1; --i) {
    for (int j = 1; i * j <= m; ++j) c[j] = a[i * j];
    ans = max(ans, Get_ans(m / i) * i);
  }
}
void work() {
  Get_mu();
  Get_ans();
}
void outo() { printf("%lld\n", ans); }
int main() {
  int T = 1;
  for (; T--;) {
    into();
    work();
    outo();
  }
  return 0;
}

```