#include <bits/stdc++.h>
using namespace std;
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  s << "{";
  for (int i = 0; i < t.size(); i++)
    s << t[i] << (i == t.size() - 1 ? "" : ",");
  return s << "}" << endl;
}
const int mxn = 100001;
int pres[mxn + 1];
int u[mxn + 1];
int sito[mxn + 2];
vector<int> d[mxn + 1];
long long cnt[mxn + 1];
long long cnt_coprime(int n) {
  long long r = 0;
  for (int e : d[n]) r += u[e] * cnt[e];
  return r;
}
void add_cnt(int n, int val) {
  for (int e : d[n]) cnt[e] += val;
}
int main() {
  ios_base::sync_with_stdio(0);
  u[1] = 1;
  for (int j = 2; j <= mxn; j++) {
    if (sito[j]) {
      int p = sito[j];
      int k = j / p;
      while (k % p == 0) {
        k /= p;
      }
      u[j] = u[k] * u[j / k];
    } else {
      for (int x = 2 * j; x <= mxn; x += j) {
        sito[x] = j;
      }
      u[j] = -1;
    }
  }
  for (int j = 1; j <= mxn; j++) {
    for (int x = j; x <= mxn; x += j) d[x].push_back(j);
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    pres[a] = 1;
  }
  long long mx = 1;
  for (int g = 1; g <= mxn; g++) {
    vector<int> s;
    for (int i = mxn / g; i >= 1; i--) {
      if (!pres[i * g]) continue;
      mx = max(mx, i * 1LL * g);
      while (cnt_coprime(i)) {
        mx = max(mx, i * g * 1LL * s.back());
        add_cnt(s.back(), -1);
        s.pop_back();
      }
      s.push_back(i);
      add_cnt(i, 1);
    }
    while ((int)(s).size()) {
      add_cnt(s.back(), -1);
      s.pop_back();
    }
  }
  cout << mx << "\n";
  return 0;
}

### 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;
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  s << "{";
  for (int i = 0; i < t.size(); i++)
    s << t[i] << (i == t.size() - 1 ? "" : ",");
  return s << "}" << endl;
}
const int mxn = 100001;
int pres[mxn + 1];
int u[mxn + 1];
int sito[mxn + 2];
vector<int> d[mxn + 1];
long long cnt[mxn + 1];
long long cnt_coprime(int n) {
  long long r = 0;
  for (int e : d[n]) r += u[e] * cnt[e];
  return r;
}
void add_cnt(int n, int val) {
  for (int e : d[n]) cnt[e] += val;
}
int main() {
  ios_base::sync_with_stdio(0);
  u[1] = 1;
  for (int j = 2; j <= mxn; j++) {
    if (sito[j]) {
      int p = sito[j];
      int k = j / p;
      while (k % p == 0) {
        k /= p;
      }
      u[j] = u[k] * u[j / k];
    } else {
      for (int x = 2 * j; x <= mxn; x += j) {
        sito[x] = j;
      }
      u[j] = -1;
    }
  }
  for (int j = 1; j <= mxn; j++) {
    for (int x = j; x <= mxn; x += j) d[x].push_back(j);
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    pres[a] = 1;
  }
  long long mx = 1;
  for (int g = 1; g <= mxn; g++) {
    vector<int> s;
    for (int i = mxn / g; i >= 1; i--) {
      if (!pres[i * g]) continue;
      mx = max(mx, i * 1LL * g);
      while (cnt_coprime(i)) {
        mx = max(mx, i * g * 1LL * s.back());
        add_cnt(s.back(), -1);
        s.pop_back();
      }
      s.push_back(i);
      add_cnt(i, 1);
    }
    while ((int)(s).size()) {
      add_cnt(s.back(), -1);
      s.pop_back();
    }
  }
  cout << mx << "\n";
  return 0;
}

```