Orac and LCM

For the multiset of positive integers $s=\{s_1,s_2,\dots,s_k\}$, define the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of $s$ as follow:

• $\gcd(s)$ is the maximum positive integer $x$, such that all integers in $s$ are divisible on $x$.
• $\textrm{lcm}(s)$ is the minimum positive integer $x$, that divisible on all integers from $s$.

For example, $\gcd(\{8,12\})=4,\gcd(\{12,18,6\})=6$ and $\textrm{lcm}(\{4,6\})=12$. Note that for any positive integer $x$, $\gcd(\{x\})=\textrm{lcm}(\{x\})=x$.

Orac has a sequence $a$ with length $n$. He come up with the multiset $t=\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\}$, and asked you to find the value of $\gcd(t)$ for him. In other words, you need to calculate the GCD of LCMs of all pairs of elements in the given sequence.Input

The first line contains one integer $n\ (2\le n\le 100\,000)$.

The second line contains $n$ integers, $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 200\,000$).Output

Print one integer: $\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$.Examplesinput

2
1 1

output

1

input

4
10 24 40 80

output

40

input

10
540 648 810 648 720 540 594 864 972 648

output

54

Note

For the first example, $t=\{\textrm{lcm}(\{1,1\})\}=\{1\}$, so $\gcd(t)=1$.

For the second example, $t=\{120,40,80,120,240,80\}$, and it’s not hard to see that $\gcd(t)=40$.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
    pref[i + 1] = __gcd(pref[i], a[i]);
  }
  vector<int> suf(n + 1);
for (int i = n - 1; i >= 0; i--) {
suf[i] = __gcd(suf[i + 1], a[i]);
}
long long ans = 1;
for (int i = 0; i < n; i++) {
    int x = __gcd(pref[i], suf[i + 1]);
    ans = ans / __gcd(ans, (long long) x) * x;
  }
  cout << ans << '\n';
  return 0;
}