#P1349A. Orac and LCM

    ID: 5341 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structuresmathnumber theory*1600

Orac and LCM

No submission language available for this problem.

Description

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.

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

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

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

Samples

2
1 1
1
4
10 24 40 80
40
10
540 648 810 648 720 540 594 864 972 648
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$.