#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 100000 + 10;
const long long MOD = 1000000000 + 7;
const long long INF = 1000000010;
const long long LOG = 25;
int n, a[N], l[N], r[N], M[N], cnt[N];
long long sm;
vector<int> num, Q[N], divi[N];
long long nCr(long long x) { return x * (x - 1) / 2; }
void add(int x) {
  for (auto u : divi[x]) {
    sm -= nCr(cnt[u]) * M[u];
    cnt[u]++;
    sm += nCr(cnt[u]) * M[u];
  }
}
void minu(int x) {
  for (auto u : divi[x]) {
    sm -= nCr(cnt[u]) * M[u];
    cnt[u]--;
    sm += nCr(cnt[u]) * M[u];
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  M[1] = 1;
  for (int i = 1; i < N; i++) {
    for (int j = i * 2; j < N; j += i) M[j] -= M[i];
  }
  cin >> n;
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) divi[j].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (auto u : divi[a[i]]) num.push_back(u);
  }
  sort(num.begin(), num.end());
  num.resize(unique(num.begin(), num.end()) - num.begin());
  for (int i = 0; i < num.size(); i++) l[i] = 0, r[i] = num.size();
  for (int lg = 0; lg < 17; lg++) {
    for (int i = 0; i <= num.size(); i++) Q[i].clear();
    for (int i = 0; i < num.size(); i++) {
      if (r[i] - l[i] == 1) continue;
      Q[(l[i] + r[i]) >> 1].push_back(i);
    }
    memset(cnt, 0, sizeof cnt);
    sm = 0;
    for (int i = num.size() - 1; i >= 0; i--) {
      add(num[i]);
      long long x = sm;
      for (auto u : Q[i]) {
        add(num[u]);
        long long y = sm;
        minu(num[u]);
        if (y > x)
          l[u] = i;
        else
          r[u] = i;
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < num.size(); i++) {
    ans = max(ans, num[i] * 1ll * num[l[i]]);
  }
  cout << ans;
  return 0;
}

### Prompt

Your task is to create 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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 100000 + 10;
const long long MOD = 1000000000 + 7;
const long long INF = 1000000010;
const long long LOG = 25;
int n, a[N], l[N], r[N], M[N], cnt[N];
long long sm;
vector<int> num, Q[N], divi[N];
long long nCr(long long x) { return x * (x - 1) / 2; }
void add(int x) {
  for (auto u : divi[x]) {
    sm -= nCr(cnt[u]) * M[u];
    cnt[u]++;
    sm += nCr(cnt[u]) * M[u];
  }
}
void minu(int x) {
  for (auto u : divi[x]) {
    sm -= nCr(cnt[u]) * M[u];
    cnt[u]--;
    sm += nCr(cnt[u]) * M[u];
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  M[1] = 1;
  for (int i = 1; i < N; i++) {
    for (int j = i * 2; j < N; j += i) M[j] -= M[i];
  }
  cin >> n;
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) divi[j].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (auto u : divi[a[i]]) num.push_back(u);
  }
  sort(num.begin(), num.end());
  num.resize(unique(num.begin(), num.end()) - num.begin());
  for (int i = 0; i < num.size(); i++) l[i] = 0, r[i] = num.size();
  for (int lg = 0; lg < 17; lg++) {
    for (int i = 0; i <= num.size(); i++) Q[i].clear();
    for (int i = 0; i < num.size(); i++) {
      if (r[i] - l[i] == 1) continue;
      Q[(l[i] + r[i]) >> 1].push_back(i);
    }
    memset(cnt, 0, sizeof cnt);
    sm = 0;
    for (int i = num.size() - 1; i >= 0; i--) {
      add(num[i]);
      long long x = sm;
      for (auto u : Q[i]) {
        add(num[u]);
        long long y = sm;
        minu(num[u]);
        if (y > x)
          l[u] = i;
        else
          r[u] = i;
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < num.size(); i++) {
    ans = max(ans, num[i] * 1ll * num[l[i]]);
  }
  cout << ans;
  return 0;
}

```