首先假设最优解是选择 $x, y$ 两个数，那么一定存在 $a ~|~ x, b ~|~ y, \gcd(a,b)=1, lcm(x,y)=lcm(a,b)=ab$。
先把 $a_i$ 的所有因数加入序列。
$10^5$ 以内因数个数最多的数是 $83160$，只有 $128$ 个因数，因此是存得下的。

暴力：对于一个数 $x$，从大到小枚举那些比它大的数，如果存在 $y,gcd(x,y)=1$ 那么就把 $xy$ 计入答案并考虑下一个 $x$。

更优雅的暴力：注意到如果存在 $a \gt b \gt c$，且 $ac$ 被计入答案，那么 $b$ 是无用的。
所以可以拿一个单调栈存储，每次从大到小扫栈里的元素，把最大的匹配数以后的全部删掉再加入当前数。
这样复杂度会稍微降低一些，但并不能保证复杂度正确。

考虑我们在干一件什么事情？
我们在用单调栈维护可能成为答案的元素，但是每次从栈底往上扫，这一听就很蠢。
我们希望的是从栈顶扫，直到扫到最大的 $y$ 满足 $gcd(x,y)=1$，在这之前的元素通通踢出去。
但是从栈顶扫并不能知道当前栈顶是不是最大的 $y$ 啊？？
其实只要知道栈里有多少个 $y$ 满足条件就行了，可是这个数量怎么求？

我们知道，$[n=1] = (\sum\limits_{d|n} \mu(d))$
所以有 $[gcd(x,y)=1] = (\sum\limits_{d | \gcd(x,y)} \mu(d))$。
我们要求：

$$\sum\limits_{y \in stack} [\gcd(x,y) = 1]$$
$$=\sum\limits_{y \in stack} \sum\limits_{d | gcd(x,y)} \mu(d)$$
$$=\sum\limits_{d | x} \mu(d) \sum\limits_{y \in stack} [d ~|~ y]$$

后面 $\sum\limits_{y \in stack} [d ~|~ y]$ 可以拿一个桶维护栈内的约数个数，$\mu$ 可以预处理。

注意预处理的时候 $\mu(1) = 1$，以及原序列那些数要选上。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 1.3e7 + 15;

int n, m, a[M];

bool st[N];
int mu[N], p[N], tot = 0;
vector<int> d[N];   //每个数的约数
void init_mu() {
    mu[1] = 1;
    for (int i = 2; i <= 100000; i++) {
        if (!st[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= 100000; j++) {
            st[i * p[j]] = 1;
            if (i % p[j] == 0) { mu[i * p[j]] = 0; break; }
            else mu[i * p[j]] = mu[i] * -1;
        }
    }
    for (int i = 1; i <= 100000; i++)
        for (int j = i; j <= 100000; j += i) d[j].push_back(i);
}

int stk[N], top = 0;
int cnt[N], now = 0, sum = 0;
long long ans = 0;

int main() {
    init_mu();
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x), ans = max(ans, 1ll * x);
        for (int j : d[x]) a[++m] = j;
    }
    sort(a + 1, a + 1 + m), m = unique(a + 1, a + 1 + m) - a - 1, reverse(a + 1, a + 1 + m);
    for (int i = 1; i <= m; i++) {
        sum = 0;
        for (int j : d[ a[i] ]) sum += mu[j] * cnt[j];
        while (sum > 0 && top > 0) {
            int delta = 0;
            for (int j : d[ stk[top] ]) {   //删除当前元素
                cnt[j]--, delta -= mu[j] * (a[i] % j == 0);    //删除对桶的贡献
            }
            if (delta != 0) ans = max(ans, a[i] * 1ll * stk[top]);
            top--, sum += delta;
        }
        stk[++top] = a[i];
        for (int j : d[ a[i] ]) cnt[j]++;
    }
    printf("%lld\n", ans);
    return 0;
}