#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
struct SieveOfEratosthenes : std::vector<int> {
  std::vector<int> primes;
  SieveOfEratosthenes(int MAXN) : std::vector<int>(MAXN + 1) {
    std::iota(begin(), end(), 0);
    for (int i = 2; i <= MAXN; i++) {
      if ((*this)[i] == i) {
        primes.push_back(i);
        for (int j = i; j <= MAXN; j += i) (*this)[j] = i;
      }
    }
  }
  using T = long long int;
  std::map<T, int> Factorize(T x) {
    assert(x <= 1LL * (int(size()) - 1) * (int(size()) - 1));
    std::map<T, int> ret;
    if (x < int(size())) {
      while (x > 1) {
        ret[(*this)[x]]++;
        x /= (*this)[x];
      }
    } else {
      for (auto p : primes) {
        while (!(x % p)) x /= p, ret[p]++;
        if (x == 1) break;
      }
      if (x > 1) ret[x]++;
    }
    return ret;
  }
  std::vector<T> Divisors(int x) {
    std::vector<T> ret{1};
    for (auto p : Factorize(x)) {
      int n = ret.size();
      for (int i = 0; i < n; i++) {
        for (T a = 1, d = 1; d <= p.second; d++) {
          a *= p.first;
          ret.push_back(ret[i] * a);
        }
      }
    }
    return ret;
  }
  std::vector<int> GenerateMoebiusFunctionTable() {
    std::vector<int> ret(size());
    for (int i = 1; i < int(size()); i++) {
      if (i == 1)
        ret[i] = 1;
      else if ((i / (*this)[i]) % (*this)[i] == 0)
        ret[i] = 0;
      else
        ret[i] = -ret[i / (*this)[i]];
    }
    return ret;
  }
};
constexpr int M = 100000;
SieveOfEratosthenes sieve(M);
int main() {
  int N;
  cin >> N;
  vector<int> B(M + 1);
  lint ret = 0;
  while (N--) {
    int a;
    cin >> a;
    mmax(ret, lint(a));
    B[a] = 1;
  }
  vector<vector<lint>> divs(M + 1);
  for (int i = (1), i_end_ = (M + 1); i < i_end_; i++)
    divs[i] = sieve.Divisors(i);
  auto moebius = sieve.GenerateMoebiusFunctionTable();
  vector<int> counter(M + 1);
  auto nb_coprime = [&](int i) {
    lint n = 0;
    for (auto x : divs[i]) {
      n += counter[x] * moebius[x];
    }
    return n;
  };
  for (int d = (1), d_end_ = (M + 1); d < d_end_; d++) {
    stack<int> st;
    for (int i = M / d; i > 0; i--)
      if (B[i * d]) {
        while (nb_coprime(i)) {
          mmax(ret, (lint)d * i * st.top());
          for (auto x : divs[st.top()]) counter[x]--;
          st.pop();
        }
        for (auto x : divs[i]) counter[x]++;
        st.push(i);
      }
    while (!st.empty()) {
      for (auto x : divs[st.top()]) counter[x]--;
      st.pop();
    }
  }
  cout << ret << endl;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
using lint = long long int;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
struct SieveOfEratosthenes : std::vector<int> {
  std::vector<int> primes;
  SieveOfEratosthenes(int MAXN) : std::vector<int>(MAXN + 1) {
    std::iota(begin(), end(), 0);
    for (int i = 2; i <= MAXN; i++) {
      if ((*this)[i] == i) {
        primes.push_back(i);
        for (int j = i; j <= MAXN; j += i) (*this)[j] = i;
      }
    }
  }
  using T = long long int;
  std::map<T, int> Factorize(T x) {
    assert(x <= 1LL * (int(size()) - 1) * (int(size()) - 1));
    std::map<T, int> ret;
    if (x < int(size())) {
      while (x > 1) {
        ret[(*this)[x]]++;
        x /= (*this)[x];
      }
    } else {
      for (auto p : primes) {
        while (!(x % p)) x /= p, ret[p]++;
        if (x == 1) break;
      }
      if (x > 1) ret[x]++;
    }
    return ret;
  }
  std::vector<T> Divisors(int x) {
    std::vector<T> ret{1};
    for (auto p : Factorize(x)) {
      int n = ret.size();
      for (int i = 0; i < n; i++) {
        for (T a = 1, d = 1; d <= p.second; d++) {
          a *= p.first;
          ret.push_back(ret[i] * a);
        }
      }
    }
    return ret;
  }
  std::vector<int> GenerateMoebiusFunctionTable() {
    std::vector<int> ret(size());
    for (int i = 1; i < int(size()); i++) {
      if (i == 1)
        ret[i] = 1;
      else if ((i / (*this)[i]) % (*this)[i] == 0)
        ret[i] = 0;
      else
        ret[i] = -ret[i / (*this)[i]];
    }
    return ret;
  }
};
constexpr int M = 100000;
SieveOfEratosthenes sieve(M);
int main() {
  int N;
  cin >> N;
  vector<int> B(M + 1);
  lint ret = 0;
  while (N--) {
    int a;
    cin >> a;
    mmax(ret, lint(a));
    B[a] = 1;
  }
  vector<vector<lint>> divs(M + 1);
  for (int i = (1), i_end_ = (M + 1); i < i_end_; i++)
    divs[i] = sieve.Divisors(i);
  auto moebius = sieve.GenerateMoebiusFunctionTable();
  vector<int> counter(M + 1);
  auto nb_coprime = [&](int i) {
    lint n = 0;
    for (auto x : divs[i]) {
      n += counter[x] * moebius[x];
    }
    return n;
  };
  for (int d = (1), d_end_ = (M + 1); d < d_end_; d++) {
    stack<int> st;
    for (int i = M / d; i > 0; i--)
      if (B[i * d]) {
        while (nb_coprime(i)) {
          mmax(ret, (lint)d * i * st.top());
          for (auto x : divs[st.top()]) counter[x]--;
          st.pop();
        }
        for (auto x : divs[i]) counter[x]++;
        st.push(i);
      }
    while (!st.empty()) {
      for (auto x : divs[st.top()]) counter[x]--;
      st.pop();
    }
  }
  cout << ret << endl;
}

```