Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Short Statement Here

By little_mod · Limits 2.5s, 512 MB

You are given an array $A$ of $n$ integers. Find all coprime pairs from $A$. Multiply each of the pairs. Find the maximum among them.

More formally, find MAX$(A_i \cdot A_j)$ where $1 \leq i < j \leq n$ and $gcd(A_i, A_j) = 1$.

Input

Input consists of two lines. First of them consists of an integer $n$ $(2 \leq n \leq 10^{6})$. Second line consists of $n$ integers $A_1, A_2, ..., A_n$ $(1 \leq A_i \leq 10^{6})$

Output

If answer doesn’t exist print $-1$. Otherwise, print one integer denoting the answer.

Samples

InputOutput
4
2 8 9 10
90

Coprime pairs are (2,9), (8,9) , (9, 10) and (2 * 9)=18, (8 * 9) = 72, (9 * 10) = 90. Maximum is 90.

InputOutput
4
2 8 10 12
-1

There is no coprime pair.


    Discussion

    Statistics


    31% Solution Ratio

    serotoninEarliest, 2w ago

    serotoninFastest, 0.3s

    serotoninLightest, 12 MB

    YouKnowWhoShortest, 1359B

    Submit

    Login to submit

    Editorial

    Prerequsite: Inclusion exclusion/mobius function, seive, stack Let’s try to solve this problem usin...