#include <bits/stdc++.h>
using namespace std;
inline int gcd(int x, int y) {
  if (x > y) swap(x, y);
  while (x) y %= x, swap(x, y);
  return y;
}
int a[100005], c[100005];
inline bool cmp(int x, int y) { return x > y; }
inline bool cmp2(int x, int y) {
  if (x % 2 == 0 && y % 2 != 0) return 0;
  if (x % 2 != 0 && y % 2 == 0) return 1;
  return x > y;
}
inline bool cmp3(int x, int y) {
  if (x % 3 == 0 && y % 3 != 0) return 0;
  if (x % 3 != 0 && y % 3 == 0) return 1;
  return x > y;
}
inline bool cmp5(int x, int y) {
  if (x % 5 == 0 && y % 5 != 0) return 0;
  if (x % 5 != 0 && y % 5 == 0) return 1;
  return x > y;
}
inline bool cmp7(int x, int y) {
  if (x % 7 == 0 && y % 7 != 0) return 0;
  if (x % 7 != 0 && y % 7 == 0) return 1;
  return x > y;
}
inline bool cmp11(int x, int y) {
  if (x % 11 == 0 && y % 11 != 0) return 0;
  if (x % 11 != 0 && y % 11 == 0) return 1;
  return x > y;
}
inline bool cmp13(int x, int y) {
  if (x % 13 == 0 && y % 13 != 0) return 0;
  if (x % 13 != 0 && y % 13 == 0) return 1;
  return x > y;
}
inline bool cmp17(int x, int y) {
  if (x % 17 == 0 && y % 17 != 0) return 0;
  if (x % 17 != 0 && y % 17 == 0) return 1;
  return x > y;
}
inline bool cmp19(int x, int y) {
  if (x % 19 == 0 && y % 19 != 0) return 0;
  if (x % 19 != 0 && y % 19 == 0) return 1;
  return x > y;
}
long long ans;
int n;
inline void qwq(int x) {
  for (int i = 1; i <= min(n, 1000 / x); i++)
    for (int j = i + 1; j <= min(n, 1000 / x); j++)
      ans = max(ans, ((long long)a[i] * a[j] / gcd(a[i], a[j])));
  for (int i = 1; i <= min(n, 2000000 / n / x); i++)
    for (int j = i + 1; j <= n; j++)
      ans = max(ans, ((long long)a[i] * a[j] / gcd(a[i], a[j])));
}
int cnt = 0;
map<int, int> mp;
int main(int argc, char** argv) {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  mp[1] = 1;
  for (int i = 1; i <= n; i++)
    if (!mp[a[i]]) mp[a[i]] = 1, a[++cnt] = a[i];
  n = cnt;
  for (int i = 1; i <= 100000; i++) {
    int x = i;
    c[i] = 1;
    for (int j = 2; j * j <= min(x, 49); j++) {
      if (x % j == 0) ++c[i];
      while (x % j == 0) x /= j;
    }
    if (x > 1 && x <= 7) ++c[i];
  }
  sort(a + 1, a + n + 1, cmp);
  ans = a[1];
  if (n > 1) {
    qwq(1);
    sort(a + 1, a + n + 1, cmp2);
    qwq(2);
    sort(a + 1, a + n + 1, cmp3);
    qwq(3);
    sort(a + 1, a + n + 1, cmp5);
    qwq(5);
    sort(a + 1, a + n + 1, cmp7);
    qwq(7);
    sort(a + 1, a + n + 1, cmp11);
    qwq(11);
    sort(a + 1, a + n + 1, cmp13);
    qwq(13);
    sort(a + 1, a + n + 1, cmp17);
    qwq(17);
    sort(a + 1, a + n + 1, cmp19);
    qwq(19);
  }
  cout << ans;
  return 0;
}

### Prompt

Please formulate 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;
inline int gcd(int x, int y) {
  if (x > y) swap(x, y);
  while (x) y %= x, swap(x, y);
  return y;
}
int a[100005], c[100005];
inline bool cmp(int x, int y) { return x > y; }
inline bool cmp2(int x, int y) {
  if (x % 2 == 0 && y % 2 != 0) return 0;
  if (x % 2 != 0 && y % 2 == 0) return 1;
  return x > y;
}
inline bool cmp3(int x, int y) {
  if (x % 3 == 0 && y % 3 != 0) return 0;
  if (x % 3 != 0 && y % 3 == 0) return 1;
  return x > y;
}
inline bool cmp5(int x, int y) {
  if (x % 5 == 0 && y % 5 != 0) return 0;
  if (x % 5 != 0 && y % 5 == 0) return 1;
  return x > y;
}
inline bool cmp7(int x, int y) {
  if (x % 7 == 0 && y % 7 != 0) return 0;
  if (x % 7 != 0 && y % 7 == 0) return 1;
  return x > y;
}
inline bool cmp11(int x, int y) {
  if (x % 11 == 0 && y % 11 != 0) return 0;
  if (x % 11 != 0 && y % 11 == 0) return 1;
  return x > y;
}
inline bool cmp13(int x, int y) {
  if (x % 13 == 0 && y % 13 != 0) return 0;
  if (x % 13 != 0 && y % 13 == 0) return 1;
  return x > y;
}
inline bool cmp17(int x, int y) {
  if (x % 17 == 0 && y % 17 != 0) return 0;
  if (x % 17 != 0 && y % 17 == 0) return 1;
  return x > y;
}
inline bool cmp19(int x, int y) {
  if (x % 19 == 0 && y % 19 != 0) return 0;
  if (x % 19 != 0 && y % 19 == 0) return 1;
  return x > y;
}
long long ans;
int n;
inline void qwq(int x) {
  for (int i = 1; i <= min(n, 1000 / x); i++)
    for (int j = i + 1; j <= min(n, 1000 / x); j++)
      ans = max(ans, ((long long)a[i] * a[j] / gcd(a[i], a[j])));
  for (int i = 1; i <= min(n, 2000000 / n / x); i++)
    for (int j = i + 1; j <= n; j++)
      ans = max(ans, ((long long)a[i] * a[j] / gcd(a[i], a[j])));
}
int cnt = 0;
map<int, int> mp;
int main(int argc, char** argv) {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  mp[1] = 1;
  for (int i = 1; i <= n; i++)
    if (!mp[a[i]]) mp[a[i]] = 1, a[++cnt] = a[i];
  n = cnt;
  for (int i = 1; i <= 100000; i++) {
    int x = i;
    c[i] = 1;
    for (int j = 2; j * j <= min(x, 49); j++) {
      if (x % j == 0) ++c[i];
      while (x % j == 0) x /= j;
    }
    if (x > 1 && x <= 7) ++c[i];
  }
  sort(a + 1, a + n + 1, cmp);
  ans = a[1];
  if (n > 1) {
    qwq(1);
    sort(a + 1, a + n + 1, cmp2);
    qwq(2);
    sort(a + 1, a + n + 1, cmp3);
    qwq(3);
    sort(a + 1, a + n + 1, cmp5);
    qwq(5);
    sort(a + 1, a + n + 1, cmp7);
    qwq(7);
    sort(a + 1, a + n + 1, cmp11);
    qwq(11);
    sort(a + 1, a + n + 1, cmp13);
    qwq(13);
    sort(a + 1, a + n + 1, cmp17);
    qwq(17);
    sort(a + 1, a + n + 1, cmp19);
    qwq(19);
  }
  cout << ans;
  return 0;
}

```