#include <bits/stdc++.h>
const int N = 100010, INF = 0x3f3f3f3f;
std::vector<int> fac[N];
int n;
int a[N];
int acnt[N], cnt[N];
int mu[N], prime[N], psum;
bool vis[N];
inline int read(void) {
  int res, f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  res = c - 48;
  while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - 48;
  return res * f;
}
inline void init(void) {
  mu[1] = 1;
  for (int i = 2; i <= N - 10; ++i) {
    if (!vis[i]) {
      prime[++psum] = i;
      mu[i] = -1;
    }
    for (int j = 1; i * prime[j] <= N - 10 && j <= psum; ++j) {
      vis[i * prime[j]] = true;
      if (i % prime[j] == 0) {
        break;
      } else {
        mu[i * prime[j]] = -mu[i];
      }
    }
  }
  return;
}
inline int getsum(int x) {
  long long res = 0;
  for (int i = 0; i < (int)fac[x].size(); ++i) {
    res += mu[fac[x][i]] * cnt[fac[x][i]];
  }
  return (int)res;
}
inline void add(int x, int y) {
  for (int i = 0; i < (int)fac[x].size(); ++i) {
    cnt[fac[x][i]] += y;
  }
  return;
}
inline int gcd(int a, int b) { return (!b) ? a : gcd(b, a % b); }
int main(void) {
  init();
  n = read();
  int A = 0;
  for (int i = 1; i <= n; ++i) {
    A = std::max(A, a[i] = read()), ++acnt[a[i]];
  }
  for (int i = 1; i <= A; ++i) {
    for (int j = 1; i * j <= A; ++j) {
      fac[i * j].push_back(i);
    }
  }
  std::stack<int> k = std::stack<int>();
  long long ans = A;
  for (int i = 1; i <= A; ++i) {
    for (int j = A / i; j; --j) {
      if (!acnt[i * j]) {
        continue;
      }
      int c = getsum(j);
      while (c) {
        int x = k.top();
        k.pop();
        if (gcd(x, j) == 1) {
          ans = std::max(ans, 1ll * i * x * j);
          --c;
        }
        add(x, -1);
      }
      add(j, 1);
      k.push(j);
    }
    while (!k.empty()) {
      int x = k.top();
      k.pop();
      add(x, -1);
    }
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 N = 100010, INF = 0x3f3f3f3f;
std::vector<int> fac[N];
int n;
int a[N];
int acnt[N], cnt[N];
int mu[N], prime[N], psum;
bool vis[N];
inline int read(void) {
  int res, f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  res = c - 48;
  while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - 48;
  return res * f;
}
inline void init(void) {
  mu[1] = 1;
  for (int i = 2; i <= N - 10; ++i) {
    if (!vis[i]) {
      prime[++psum] = i;
      mu[i] = -1;
    }
    for (int j = 1; i * prime[j] <= N - 10 && j <= psum; ++j) {
      vis[i * prime[j]] = true;
      if (i % prime[j] == 0) {
        break;
      } else {
        mu[i * prime[j]] = -mu[i];
      }
    }
  }
  return;
}
inline int getsum(int x) {
  long long res = 0;
  for (int i = 0; i < (int)fac[x].size(); ++i) {
    res += mu[fac[x][i]] * cnt[fac[x][i]];
  }
  return (int)res;
}
inline void add(int x, int y) {
  for (int i = 0; i < (int)fac[x].size(); ++i) {
    cnt[fac[x][i]] += y;
  }
  return;
}
inline int gcd(int a, int b) { return (!b) ? a : gcd(b, a % b); }
int main(void) {
  init();
  n = read();
  int A = 0;
  for (int i = 1; i <= n; ++i) {
    A = std::max(A, a[i] = read()), ++acnt[a[i]];
  }
  for (int i = 1; i <= A; ++i) {
    for (int j = 1; i * j <= A; ++j) {
      fac[i * j].push_back(i);
    }
  }
  std::stack<int> k = std::stack<int>();
  long long ans = A;
  for (int i = 1; i <= A; ++i) {
    for (int j = A / i; j; --j) {
      if (!acnt[i * j]) {
        continue;
      }
      int c = getsum(j);
      while (c) {
        int x = k.top();
        k.pop();
        if (gcd(x, j) == 1) {
          ans = std::max(ans, 1ll * i * x * j);
          --c;
        }
        add(x, -1);
      }
      add(j, 1);
      k.push(j);
    }
    while (!k.empty()) {
      int x = k.top();
      k.pop();
      add(x, -1);
    }
  }
  printf("%lld", ans);
  return 0;
}

```