#include <bits/stdc++.h>
using namespace std;
int lsb(int x) { return x & -x; }
void Merge(vector<int>& A, vector<int>& B, vector<int>& C,
           const vector<int>& left_pair) {
  vector<int>().swap(C);
  C.resize(A.size() + B.size());
  int i = 0, j = 0, sz = 0;
  while (i < (int)A.size() or j < (int)B.size()) {
    if (i == (int)A.size())
      C[sz++] = B[j++];
    else if (j == (int)B.size())
      C[sz++] = A[i++];
    else {
      if (left_pair[A[i]] < left_pair[B[j]])
        C[sz++] = A[i++];
      else
        C[sz++] = B[j++];
    }
  }
  while (i < (int)A.size()) C[sz++] = A[i++];
  while (j < (int)B.size()) C[sz++] = B[j++];
}
int main() {
  const int N = 1e5;
  vector<int> bits(N + 1), lg2(N + 1);
  for (int i = 2; i <= N; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= N; ++i) {
    bits[i] = bits[i >> 1] + (i & 1);
  }
  vector<int> low(N + 1, -1), sqfree(N + 1, 1);
  for (int i = 2; i <= N; ++i) {
    if (low[i] == -1) {
      for (int j = i; j <= N; j += i) {
        if (low[j] == -1)
          low[j] = i;
        else
          low[j] = min(low[j], i);
        sqfree[j] *= i;
      }
    }
  }
  auto decomp = [&](int x) {
    x = sqfree[x];
    vector<int> v;
    while (x > 1) {
      v.push_back(low[x]);
      x /= low[x];
    }
    return v;
  };
  ios::sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> inp(N + 1);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    inp[x]++;
    if (inp[x] >= 2) ans = max(ans, (long long)x);
  }
  auto add = [&](int x, int d, vector<int>& cnt) {
    vector<int> f = decomp(x), prod(1 << f.size(), 1);
    int res = 0;
    for (int i = 1; i < 1 << f.size(); ++i) {
      int b = lg2[lsb(i)];
      prod[i] = prod[i ^ (1 << b)] * f[b];
      cnt[prod[i]] += d;
    }
  };
  auto not_coprime = [&](int x, vector<int>& cnt) {
    vector<int> f = decomp(x), prod(1 << f.size(), 1);
    int res = 0;
    for (int i = 1; i < 1 << f.size(); ++i) {
      int b = lg2[lsb(i)];
      prod[i] = prod[i ^ (1 << b)] * f[b];
      if (bits[i] & 1)
        res += cnt[prod[i]];
      else
        res -= cnt[prod[i]];
    }
    return res;
  };
  for (int g = 1; g <= N; ++g) {
    vector<int> v;
    vector<int> vis(N / g + 1);
    for (int i = N / g; i >= 1; --i) {
      if (inp[i * g] >= 1 && !vis[sqfree[i]]) {
        v.push_back(i);
        vis[sqfree[i]] = 1;
      }
    }
    if (v.size() < 2) continue;
    if ((long long)v[0] * v[1] * g <= ans) continue;
    reverse(v.begin(), v.end());
    vector<int> many(N / g + 1), cnt(N / g + 1);
    for (int i = 0; i < (int)v.size(); ++i) {
      many[v[i]] = i - not_coprime(v[i], cnt);
      add(v[i], +1, cnt);
    }
    for (int i = 0; i < (int)v.size(); ++i) add(v[i], -1, cnt);
    vector<int> left_pair(N / g + 1);
    for (int i = 1; i <= N / g; ++i) left_pair[i] = i;
    vector<int> order = v;
    for (int b = 16; b >= 0; b--) {
      if ((1 << b) > left_pair[order.back()]) continue;
      vector<int> X, Y;
      int j = 0;
      for (int i : order) {
        while (j < (int)v.size() && v[j] <= left_pair[i] - (1 << b)) {
          add(v[j], +1, cnt);
          ++j;
        }
        if (j != 0 and many[i] != 0 and j - not_coprime(i, cnt) == many[i]) {
          left_pair[i] -= 1 << b;
          X.push_back(i);
        } else
          Y.push_back(i);
      }
      for (int clr = 1; clr <= N / g; ++clr) cnt[clr] = 0;
      Merge(X, Y, order, left_pair);
    }
    for (int val : v)
      if (many[val] >= 1 and left_pair[val] != val)
        ans = max(ans, (long long)val * g * left_pair[val]);
  }
  cout << ans;
  return 0;
}

### Prompt

Your challenge is to write 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 lsb(int x) { return x & -x; }
void Merge(vector<int>& A, vector<int>& B, vector<int>& C,
           const vector<int>& left_pair) {
  vector<int>().swap(C);
  C.resize(A.size() + B.size());
  int i = 0, j = 0, sz = 0;
  while (i < (int)A.size() or j < (int)B.size()) {
    if (i == (int)A.size())
      C[sz++] = B[j++];
    else if (j == (int)B.size())
      C[sz++] = A[i++];
    else {
      if (left_pair[A[i]] < left_pair[B[j]])
        C[sz++] = A[i++];
      else
        C[sz++] = B[j++];
    }
  }
  while (i < (int)A.size()) C[sz++] = A[i++];
  while (j < (int)B.size()) C[sz++] = B[j++];
}
int main() {
  const int N = 1e5;
  vector<int> bits(N + 1), lg2(N + 1);
  for (int i = 2; i <= N; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= N; ++i) {
    bits[i] = bits[i >> 1] + (i & 1);
  }
  vector<int> low(N + 1, -1), sqfree(N + 1, 1);
  for (int i = 2; i <= N; ++i) {
    if (low[i] == -1) {
      for (int j = i; j <= N; j += i) {
        if (low[j] == -1)
          low[j] = i;
        else
          low[j] = min(low[j], i);
        sqfree[j] *= i;
      }
    }
  }
  auto decomp = [&](int x) {
    x = sqfree[x];
    vector<int> v;
    while (x > 1) {
      v.push_back(low[x]);
      x /= low[x];
    }
    return v;
  };
  ios::sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> inp(N + 1);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    inp[x]++;
    if (inp[x] >= 2) ans = max(ans, (long long)x);
  }
  auto add = [&](int x, int d, vector<int>& cnt) {
    vector<int> f = decomp(x), prod(1 << f.size(), 1);
    int res = 0;
    for (int i = 1; i < 1 << f.size(); ++i) {
      int b = lg2[lsb(i)];
      prod[i] = prod[i ^ (1 << b)] * f[b];
      cnt[prod[i]] += d;
    }
  };
  auto not_coprime = [&](int x, vector<int>& cnt) {
    vector<int> f = decomp(x), prod(1 << f.size(), 1);
    int res = 0;
    for (int i = 1; i < 1 << f.size(); ++i) {
      int b = lg2[lsb(i)];
      prod[i] = prod[i ^ (1 << b)] * f[b];
      if (bits[i] & 1)
        res += cnt[prod[i]];
      else
        res -= cnt[prod[i]];
    }
    return res;
  };
  for (int g = 1; g <= N; ++g) {
    vector<int> v;
    vector<int> vis(N / g + 1);
    for (int i = N / g; i >= 1; --i) {
      if (inp[i * g] >= 1 && !vis[sqfree[i]]) {
        v.push_back(i);
        vis[sqfree[i]] = 1;
      }
    }
    if (v.size() < 2) continue;
    if ((long long)v[0] * v[1] * g <= ans) continue;
    reverse(v.begin(), v.end());
    vector<int> many(N / g + 1), cnt(N / g + 1);
    for (int i = 0; i < (int)v.size(); ++i) {
      many[v[i]] = i - not_coprime(v[i], cnt);
      add(v[i], +1, cnt);
    }
    for (int i = 0; i < (int)v.size(); ++i) add(v[i], -1, cnt);
    vector<int> left_pair(N / g + 1);
    for (int i = 1; i <= N / g; ++i) left_pair[i] = i;
    vector<int> order = v;
    for (int b = 16; b >= 0; b--) {
      if ((1 << b) > left_pair[order.back()]) continue;
      vector<int> X, Y;
      int j = 0;
      for (int i : order) {
        while (j < (int)v.size() && v[j] <= left_pair[i] - (1 << b)) {
          add(v[j], +1, cnt);
          ++j;
        }
        if (j != 0 and many[i] != 0 and j - not_coprime(i, cnt) == many[i]) {
          left_pair[i] -= 1 << b;
          X.push_back(i);
        } else
          Y.push_back(i);
      }
      for (int clr = 1; clr <= N / g; ++clr) cnt[clr] = 0;
      Merge(X, Y, order, left_pair);
    }
    for (int val : v)
      if (many[val] >= 1 and left_pair[val] != val)
        ans = max(ans, (long long)val * g * left_pair[val]);
  }
  cout << ans;
  return 0;
}

```