#include <bits/stdc++.h>
using namespace std;
inline void using_file(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
mt19937 gen_rand;
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &a) {
  os << "(";
  os << a.first << ", ";
  os << a.second;
  os << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
  os << "{";
  bool was = false;
  for (auto &x : a) {
    if (was) {
      os << ", ";
    }
    was = true;
    os << x;
  }
  os << "}";
  return os;
}
template <typename T>
inline void debug(const char *sdbg, T x) {
  cerr << "The value of " << sdbg << " is " << x << "\n";
};
template <typename T, typename... U>
inline void debug(const char *sdbg, T h, U... t) {
  cerr << "The value of ";
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << " is " << h << "\n";
  debug(sdbg + 1, t...);
  cerr << "\n";
}
template <typename T>
T abs(T x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}
template <typename T>
T sqr(T x) {
  return x * x;
};
const long long INF_FOR_SHORT_TIME = (long long)(1e9);
template <typename T>
T mul(T a, T b, T m) {
  if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
    return (a * b) % m;
  }
  T q = (long long)((long double)a * (long double)b / (long double)m);
  T r = a * b - q * m;
  return (r + 5 * m) % m;
}
template <typename T, typename U>
T binpow(T a, U n, T MOD) {
  T res = 1;
  while (n) {
    if (n & 1) {
      res = mul(res, a, MOD);
    }
    a = mul(a, a, MOD);
    n >>= 1;
  }
  return res;
};
template <typename T>
int sign(T x) {
  if (x < 0) {
    return -1;
  } else if (x > 0) {
    return 1;
  } else {
    return 0;
  }
};
template <typename T>
T gcd(T a, T b) {
  if (a > b) {
    swap(a, b);
  }
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
};
template <typename T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
};
const int maxn = int(1e5) + 1;
const int maxk = 7;
vector<int> p[maxn] = {};
int s[maxn][1 << maxk];
int koor[1 << maxk] = {};
void pcalc() {
  for (int x = 1; x < maxn; ++x) {
    int cur = x;
    for (int y = 2; y * y <= x; ++y) {
      if (cur % y) {
        continue;
      }
      p[x].push_back(y);
      while (cur % y == 0) {
        cur /= y;
      }
    }
    if (cur > 1) {
      p[x].push_back(cur);
    }
  }
  for (int x = 1; x < maxn; ++x) {
    int n = int((p[x]).size());
    for (int mask = 1; mask < (1 << n); ++mask) {
      int res = 1;
      for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1) {
          res *= p[x][i];
        }
      }
      s[x][mask] = res;
    }
  }
  for (int mask = 0; mask < (1 << maxk); ++mask) {
    koor[mask] = (__builtin_popcount(mask) % 2 ? 1 : -1);
  }
}
vector<int> pos[maxn] = {};
vector<int> d[maxn] = {};
int used[maxn] = {};
int main() {
  gen_rand.seed(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  pcalc();
  int n;
  cin >> n;
  long long res = -1;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if (used[x]) {
      uax(res, 1LL * x);
    }
    used[x] = 1;
  }
  for (int x = maxn - 1; x >= 0; --x) {
    if (!used[x]) {
      continue;
    }
    for (int y = 1; y * y <= x; ++y) {
      if (x % y) {
        continue;
      }
      d[y].push_back(x / y);
      if (y * y != x) {
        d[x / y].push_back(y);
      }
    }
  }
  for (int g = 1; g < maxn; ++g) {
    int st = int((d[g]).size());
    for (int ind = 0; ind < int((d[g]).size()); ++ind) {
      int x = d[g][ind];
      while (st > 0 && 1LL * x * d[g][st - 1] * g < res) {
        --st;
      }
      n = int((p[x]).size());
      int l = -1;
      int r = min(ind, st);
      while (l + 1 < r) {
        int m = (l + r) / 2;
        int cnt = 0;
        for (int mask = 1; mask < (1 << n); ++mask) {
          int wl = -1;
          int wr = int((pos[s[x][mask]]).size());
          while (wl + 1 < wr) {
            int wm = (wl + wr) / 2;
            if (pos[s[x][mask]][wm] > m) {
              wr = wm;
            } else {
              wl = wm;
            }
          }
          cnt += (wl + 1) * koor[mask];
        }
        if (cnt >= m + 1) {
          l = m;
        } else {
          r = m;
        }
      }
      if (r < min(ind, st)) {
        uax(res, 1LL * x * d[g][r] * g);
      }
      for (int mask = 1; mask < (1 << n); ++mask) {
        pos[s[x][mask]].push_back(ind);
      }
    }
    for (int x : d[g]) {
      n = int((p[x]).size());
      for (int mask = 1; mask < (1 << n); ++mask) {
        pos[s[x][mask]].pop_back();
      }
    }
  }
  cout << res << "\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;
inline void using_file(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
mt19937 gen_rand;
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &a) {
  os << "(";
  os << a.first << ", ";
  os << a.second;
  os << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
  os << "{";
  bool was = false;
  for (auto &x : a) {
    if (was) {
      os << ", ";
    }
    was = true;
    os << x;
  }
  os << "}";
  return os;
}
template <typename T>
inline void debug(const char *sdbg, T x) {
  cerr << "The value of " << sdbg << " is " << x << "\n";
};
template <typename T, typename... U>
inline void debug(const char *sdbg, T h, U... t) {
  cerr << "The value of ";
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << " is " << h << "\n";
  debug(sdbg + 1, t...);
  cerr << "\n";
}
template <typename T>
T abs(T x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}
template <typename T>
T sqr(T x) {
  return x * x;
};
const long long INF_FOR_SHORT_TIME = (long long)(1e9);
template <typename T>
T mul(T a, T b, T m) {
  if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
    return (a * b) % m;
  }
  T q = (long long)((long double)a * (long double)b / (long double)m);
  T r = a * b - q * m;
  return (r + 5 * m) % m;
}
template <typename T, typename U>
T binpow(T a, U n, T MOD) {
  T res = 1;
  while (n) {
    if (n & 1) {
      res = mul(res, a, MOD);
    }
    a = mul(a, a, MOD);
    n >>= 1;
  }
  return res;
};
template <typename T>
int sign(T x) {
  if (x < 0) {
    return -1;
  } else if (x > 0) {
    return 1;
  } else {
    return 0;
  }
};
template <typename T>
T gcd(T a, T b) {
  if (a > b) {
    swap(a, b);
  }
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
};
template <typename T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
};
const int maxn = int(1e5) + 1;
const int maxk = 7;
vector<int> p[maxn] = {};
int s[maxn][1 << maxk];
int koor[1 << maxk] = {};
void pcalc() {
  for (int x = 1; x < maxn; ++x) {
    int cur = x;
    for (int y = 2; y * y <= x; ++y) {
      if (cur % y) {
        continue;
      }
      p[x].push_back(y);
      while (cur % y == 0) {
        cur /= y;
      }
    }
    if (cur > 1) {
      p[x].push_back(cur);
    }
  }
  for (int x = 1; x < maxn; ++x) {
    int n = int((p[x]).size());
    for (int mask = 1; mask < (1 << n); ++mask) {
      int res = 1;
      for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1) {
          res *= p[x][i];
        }
      }
      s[x][mask] = res;
    }
  }
  for (int mask = 0; mask < (1 << maxk); ++mask) {
    koor[mask] = (__builtin_popcount(mask) % 2 ? 1 : -1);
  }
}
vector<int> pos[maxn] = {};
vector<int> d[maxn] = {};
int used[maxn] = {};
int main() {
  gen_rand.seed(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  pcalc();
  int n;
  cin >> n;
  long long res = -1;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if (used[x]) {
      uax(res, 1LL * x);
    }
    used[x] = 1;
  }
  for (int x = maxn - 1; x >= 0; --x) {
    if (!used[x]) {
      continue;
    }
    for (int y = 1; y * y <= x; ++y) {
      if (x % y) {
        continue;
      }
      d[y].push_back(x / y);
      if (y * y != x) {
        d[x / y].push_back(y);
      }
    }
  }
  for (int g = 1; g < maxn; ++g) {
    int st = int((d[g]).size());
    for (int ind = 0; ind < int((d[g]).size()); ++ind) {
      int x = d[g][ind];
      while (st > 0 && 1LL * x * d[g][st - 1] * g < res) {
        --st;
      }
      n = int((p[x]).size());
      int l = -1;
      int r = min(ind, st);
      while (l + 1 < r) {
        int m = (l + r) / 2;
        int cnt = 0;
        for (int mask = 1; mask < (1 << n); ++mask) {
          int wl = -1;
          int wr = int((pos[s[x][mask]]).size());
          while (wl + 1 < wr) {
            int wm = (wl + wr) / 2;
            if (pos[s[x][mask]][wm] > m) {
              wr = wm;
            } else {
              wl = wm;
            }
          }
          cnt += (wl + 1) * koor[mask];
        }
        if (cnt >= m + 1) {
          l = m;
        } else {
          r = m;
        }
      }
      if (r < min(ind, st)) {
        uax(res, 1LL * x * d[g][r] * g);
      }
      for (int mask = 1; mask < (1 << n); ++mask) {
        pos[s[x][mask]].push_back(ind);
      }
    }
    for (int x : d[g]) {
      n = int((p[x]).size());
      for (int mask = 1; mask < (1 << n); ++mask) {
        pos[s[x][mask]].pop_back();
      }
    }
  }
  cout << res << "\n";
  return 0;
}

```