#include <bits/stdc++.h>
using namespace std;
int sgn(int a) {
  if (a > 0)
    return 1;
  else if (a == 0)
    return 0;
  return -1;
}
const int MX = 1e5 + 99;
vector<int> prime_divisors[MX];
vector<int> divisible_by_this[MX];
vector<int> generate_sq_free_divisors(int N) {
  vector<int> p = prime_divisors[N];
  int k = p.size();
  int MASK = 1 << k;
  vector<int> ans(MASK);
  for (int mask = 0; mask < MASK; mask++) {
    int prod = 1;
    for (int j = 0; j < k; j++) {
      if ((mask >> j) & 1) {
        prod *= -p[j];
      }
    }
    ans[mask] = prod;
  }
  return ans;
}
void init_prime_divs(void) {
  for (int N = 1; N < MX; N++) {
    int NN = N;
    for (int d = 2; d * d <= NN; d++) {
      if (NN % d != 0) continue;
      prime_divisors[N].push_back(d);
      while (NN % d == 0) NN /= d;
    }
    if (NN != 1) prime_divisors[N].push_back(NN);
  }
}
int gcd(int a, int b) {
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int query_good(const vector<int>& pp, int idx) {
  int result = 0;
  for (int d : pp) {
    int dd = abs(d), ss = sgn(d);
    auto it = upper_bound(divisible_by_this[dd].begin(),
                          divisible_by_this[dd].end(), idx);
    int cnt = it - divisible_by_this[dd].begin();
    result += cnt * ss;
  }
  return result;
}
long long solve_gcd_1(const vector<int>& V) {
  int K = V.size();
  if (K <= 1) return 0;
  int last = V.back();
  for (int i = 0; i <= last; i++) divisible_by_this[i].clear();
  long long res_fast = 0;
  for (int i = 0; i < K; i++) {
    vector<int> pp = generate_sq_free_divisors(V[i]);
    if (i > 0) {
      int R = i - 1;
      int res_R = query_good(pp, R);
      if (res_R > 0) {
        int L = 0;
        while (R > L) {
          int M = (L + R + 0) / 2;
          if (query_good(pp, M) == res_R)
            R = M;
          else
            L = M + 1;
        }
        res_fast = max(res_fast, V[i] * 1LL * V[L]);
      }
    }
    for (int d : pp) divisible_by_this[abs(d)].push_back(i);
  }
  return res_fast;
}
int n;
int a[MX];
int cnt[MX] = {0};
long long solve() {
  init_prime_divs();
  long long result = 0LL;
  for (int i = 0; i < n; i++) {
    if (cnt[a[i]]) result = max(result, (long long)a[i]);
    cnt[a[i]] = 1;
  }
  for (int G = 1; G < MX; G++) {
    vector<int> V;
    V.reserve(MX / G);
    for (int i = 1; i * G < MX; i++) {
      if (cnt[i * G]) V.push_back(i);
    }
    int sz = V.size();
    if (sz >= 2 && V[sz - 2] * 1LL * V[sz - 1] >= result) {
      long long res = solve_gcd_1(V);
      result = max(result, res * G);
    }
  }
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long res = solve();
  cout << res;
  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;
int sgn(int a) {
  if (a > 0)
    return 1;
  else if (a == 0)
    return 0;
  return -1;
}
const int MX = 1e5 + 99;
vector<int> prime_divisors[MX];
vector<int> divisible_by_this[MX];
vector<int> generate_sq_free_divisors(int N) {
  vector<int> p = prime_divisors[N];
  int k = p.size();
  int MASK = 1 << k;
  vector<int> ans(MASK);
  for (int mask = 0; mask < MASK; mask++) {
    int prod = 1;
    for (int j = 0; j < k; j++) {
      if ((mask >> j) & 1) {
        prod *= -p[j];
      }
    }
    ans[mask] = prod;
  }
  return ans;
}
void init_prime_divs(void) {
  for (int N = 1; N < MX; N++) {
    int NN = N;
    for (int d = 2; d * d <= NN; d++) {
      if (NN % d != 0) continue;
      prime_divisors[N].push_back(d);
      while (NN % d == 0) NN /= d;
    }
    if (NN != 1) prime_divisors[N].push_back(NN);
  }
}
int gcd(int a, int b) {
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int query_good(const vector<int>& pp, int idx) {
  int result = 0;
  for (int d : pp) {
    int dd = abs(d), ss = sgn(d);
    auto it = upper_bound(divisible_by_this[dd].begin(),
                          divisible_by_this[dd].end(), idx);
    int cnt = it - divisible_by_this[dd].begin();
    result += cnt * ss;
  }
  return result;
}
long long solve_gcd_1(const vector<int>& V) {
  int K = V.size();
  if (K <= 1) return 0;
  int last = V.back();
  for (int i = 0; i <= last; i++) divisible_by_this[i].clear();
  long long res_fast = 0;
  for (int i = 0; i < K; i++) {
    vector<int> pp = generate_sq_free_divisors(V[i]);
    if (i > 0) {
      int R = i - 1;
      int res_R = query_good(pp, R);
      if (res_R > 0) {
        int L = 0;
        while (R > L) {
          int M = (L + R + 0) / 2;
          if (query_good(pp, M) == res_R)
            R = M;
          else
            L = M + 1;
        }
        res_fast = max(res_fast, V[i] * 1LL * V[L]);
      }
    }
    for (int d : pp) divisible_by_this[abs(d)].push_back(i);
  }
  return res_fast;
}
int n;
int a[MX];
int cnt[MX] = {0};
long long solve() {
  init_prime_divs();
  long long result = 0LL;
  for (int i = 0; i < n; i++) {
    if (cnt[a[i]]) result = max(result, (long long)a[i]);
    cnt[a[i]] = 1;
  }
  for (int G = 1; G < MX; G++) {
    vector<int> V;
    V.reserve(MX / G);
    for (int i = 1; i * G < MX; i++) {
      if (cnt[i * G]) V.push_back(i);
    }
    int sz = V.size();
    if (sz >= 2 && V[sz - 2] * 1LL * V[sz - 1] >= result) {
      long long res = solve_gcd_1(V);
      result = max(result, res * G);
    }
  }
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long res = solve();
  cout << res;
  return 0;
}

```