CF1349A · Orac and LCM

• 难度：1600
• 标签：data structures、math、number theory
• 链接：https://codeforces.com/problemset/problem/1349/A
• 时间限制：3 seconds　内存限制：256 megabytes
• 出现位置：假期自习包/A-数学基础(快速幂/筛法/gcd/组合数取模)

英文原题面

Statement

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 \lt 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 \lt j\})$.

样例

样例 1

输入：

2
1 1

输出：

1

样例 2

输入：

4
10 24 40 80

输出：

40

样例 3

输入：

10
540 648 810 648 720 540 594 864 972 648

输出：

54

样例解释（英文原文）

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$.