#include <bits/stdc++.h>
const int C = 100001;
using ll = long long;
int dp[C], p[C], ptr[C], presence[C], alld = 0;
ll all[C];
void supfactor(int *pr, int v) {
  int i, j;
  pr[1] = 1;
  for (i = 2; i * i < v; i++) {
    if (pr[i] == 0) {
      for (j = i; j < v; j += i)
        if (pr[j] == 0) pr[j] = i;
    }
  }
  for (; i < v; i++)
    if (pr[i] == 0) pr[i] = i;
}
void transformation(int *ptr, int *pr, int v) {
  int i, mass, s = 1;
  ptr[1] = 1;
  for (i = 2; i < v; i++) {
    ptr[i] = 1;
    s = 1;
    mass = i;
    while (pr[mass] > 1) {
      if (pr[mass] != s) ptr[i] *= pr[mass];
      s = pr[mass];
      mass /= pr[mass];
    }
  }
}
int facgcd(int a, int b, int *pr) {
  int res = 1;
  while (pr[a] != 1 && pr[b] != 1) {
    if (pr[a] == pr[b])
      res *= pr[a], a /= pr[a], b /= pr[b];
    else if (pr[a] < pr[b])
      a /= pr[a];
    else
      b /= pr[b];
  }
  return res;
}
int ind[C];
ll coprime_finder(int *ex, int v, ll *mx, int mxite, int *ptr, int *pr) {
  ll res = 0;
  int i, j;
  for (i = 0; i < v; i++) ind[i] = mxite - 1;
  for (i = 1; i < v; i++) {
    for (j = ind[i]; j >= 0; j--) {
      if (facgcd(ptr[mx[j]], ptr[i], pr) == 1) break;
    }
    ind[i] = j;
    if (ex[i] == 1 && ind[i] >= 0)
      res = ((res < mx[ind[i]] * i) ? (mx[ind[i]] * i) : (res));
    for (j = i; j < v; j += i)
      ind[j] = ((ind[i] < ind[j]) ? (ind[i]) : (ind[j]));
  }
  return res;
}
int main() {
  int n, i = 0, a, j = 0, end;
  ll res = 0, subres;
  supfactor(p, C);
  transformation(ptr, p, C);
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    dp[a] = 1;
  }
  for (i = 1; i < C; i++) {
    alld = 0;
    end = C / i + ((i > 1) ? 1 : 0);
    for (j = 0; j < end; j += 1) presence[j] = 0;
    for (j = i; j < C; j += i) {
      if (dp[j] == 1) presence[j / i] = 1, all[alld] = j / i, alld++;
    }
    subres = coprime_finder(presence, end, all, alld, ptr, p);
    res = ((res < subres * i) ? (subres * i) : (res));
  }
  printf("%lld\n", res);
  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>
const int C = 100001;
using ll = long long;
int dp[C], p[C], ptr[C], presence[C], alld = 0;
ll all[C];
void supfactor(int *pr, int v) {
  int i, j;
  pr[1] = 1;
  for (i = 2; i * i < v; i++) {
    if (pr[i] == 0) {
      for (j = i; j < v; j += i)
        if (pr[j] == 0) pr[j] = i;
    }
  }
  for (; i < v; i++)
    if (pr[i] == 0) pr[i] = i;
}
void transformation(int *ptr, int *pr, int v) {
  int i, mass, s = 1;
  ptr[1] = 1;
  for (i = 2; i < v; i++) {
    ptr[i] = 1;
    s = 1;
    mass = i;
    while (pr[mass] > 1) {
      if (pr[mass] != s) ptr[i] *= pr[mass];
      s = pr[mass];
      mass /= pr[mass];
    }
  }
}
int facgcd(int a, int b, int *pr) {
  int res = 1;
  while (pr[a] != 1 && pr[b] != 1) {
    if (pr[a] == pr[b])
      res *= pr[a], a /= pr[a], b /= pr[b];
    else if (pr[a] < pr[b])
      a /= pr[a];
    else
      b /= pr[b];
  }
  return res;
}
int ind[C];
ll coprime_finder(int *ex, int v, ll *mx, int mxite, int *ptr, int *pr) {
  ll res = 0;
  int i, j;
  for (i = 0; i < v; i++) ind[i] = mxite - 1;
  for (i = 1; i < v; i++) {
    for (j = ind[i]; j >= 0; j--) {
      if (facgcd(ptr[mx[j]], ptr[i], pr) == 1) break;
    }
    ind[i] = j;
    if (ex[i] == 1 && ind[i] >= 0)
      res = ((res < mx[ind[i]] * i) ? (mx[ind[i]] * i) : (res));
    for (j = i; j < v; j += i)
      ind[j] = ((ind[i] < ind[j]) ? (ind[i]) : (ind[j]));
  }
  return res;
}
int main() {
  int n, i = 0, a, j = 0, end;
  ll res = 0, subres;
  supfactor(p, C);
  transformation(ptr, p, C);
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    dp[a] = 1;
  }
  for (i = 1; i < C; i++) {
    alld = 0;
    end = C / i + ((i > 1) ? 1 : 0);
    for (j = 0; j < end; j += 1) presence[j] = 0;
    for (j = i; j < C; j += i) {
      if (dp[j] == 1) presence[j / i] = 1, all[alld] = j / i, alld++;
    }
    subres = coprime_finder(presence, end, all, alld, ptr, p);
    res = ((res < subres * i) ? (subres * i) : (res));
  }
  printf("%lld\n", res);
  return 0;
}

```