#include <bits/stdc++.h>
long long max(long long a, long long b) { return a > b ? a : b; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int mobius[100000 + 1], dd[100000 + 1][128], kk[100000 + 1];
void init() {
  int a, b;
  mobius[1] = 1;
  for (a = 2; a <= 100000; a++) {
    if (mobius[a]) continue;
    for (b = a; b <= 100000; b += a) mobius[b]++;
  }
  for (a = 1; a <= 100000; a++)
    for (b = a; b <= 100000; b += a) dd[b][kk[b]++] = a;
  for (a = 2; a <= 100000 / a; a++)
    for (b = a * a; b <= 100000; b += a * a) mobius[b] = 0;
  for (a = 2; a <= 100000; a++)
    if (mobius[a] != 0) mobius[a] = mobius[a] % 2 == 0 ? 1 : -1;
}
int xx[100000 + 1];
void update(int a, int x) {
  int i;
  for (i = 0; i < kk[a]; i++) {
    int d = dd[a][i];
    xx[d] += x;
  }
}
int query(int a) {
  int i, x = 0;
  for (i = 0; i < kk[a]; i++) {
    int d = dd[a][i];
    x += xx[d] * mobius[d];
  }
  return x;
}
int main() {
  static char used[100000 + 1];
  static int qu[100000];
  int n, d, i, cnt;
  long long ans;
  init();
  scanf("%d", &n);
  ans = 0;
  while (n--) {
    int a;
    scanf("%d", &a);
    used[a] = 1;
    ans = max(ans, a);
  }
  for (d = 1; d <= 100000; d++) {
    cnt = 0;
    for (i = 100000 / d; i > 0; i--) {
      int k;
      if (!used[i * d]) continue;
      k = query(i);
      while (k > 0) {
        if (gcd(qu[cnt - 1], i) == 1) {
          ans = max(ans, (long long)i * qu[cnt - 1] * d);
          k--;
        }
        update(qu[--cnt], -1);
      }
      update(qu[cnt++] = i, 1);
    }
    while (cnt) update(qu[--cnt], -1);
  }
  printf("%lld\n", ans);
  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>
long long max(long long a, long long b) { return a > b ? a : b; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int mobius[100000 + 1], dd[100000 + 1][128], kk[100000 + 1];
void init() {
  int a, b;
  mobius[1] = 1;
  for (a = 2; a <= 100000; a++) {
    if (mobius[a]) continue;
    for (b = a; b <= 100000; b += a) mobius[b]++;
  }
  for (a = 1; a <= 100000; a++)
    for (b = a; b <= 100000; b += a) dd[b][kk[b]++] = a;
  for (a = 2; a <= 100000 / a; a++)
    for (b = a * a; b <= 100000; b += a * a) mobius[b] = 0;
  for (a = 2; a <= 100000; a++)
    if (mobius[a] != 0) mobius[a] = mobius[a] % 2 == 0 ? 1 : -1;
}
int xx[100000 + 1];
void update(int a, int x) {
  int i;
  for (i = 0; i < kk[a]; i++) {
    int d = dd[a][i];
    xx[d] += x;
  }
}
int query(int a) {
  int i, x = 0;
  for (i = 0; i < kk[a]; i++) {
    int d = dd[a][i];
    x += xx[d] * mobius[d];
  }
  return x;
}
int main() {
  static char used[100000 + 1];
  static int qu[100000];
  int n, d, i, cnt;
  long long ans;
  init();
  scanf("%d", &n);
  ans = 0;
  while (n--) {
    int a;
    scanf("%d", &a);
    used[a] = 1;
    ans = max(ans, a);
  }
  for (d = 1; d <= 100000; d++) {
    cnt = 0;
    for (i = 100000 / d; i > 0; i--) {
      int k;
      if (!used[i * d]) continue;
      k = query(i);
      while (k > 0) {
        if (gcd(qu[cnt - 1], i) == 1) {
          ans = max(ans, (long long)i * qu[cnt - 1] * d);
          k--;
        }
        update(qu[--cnt], -1);
      }
      update(qu[cnt++] = i, 1);
    }
    while (cnt) update(qu[--cnt], -1);
  }
  printf("%lld\n", ans);
  return 0;
}

```