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

### Statistics

31% Solution Ratio

serotoninEarliest, 2w ago

serotoninFastest, 0.3s

serotoninLightest, 12 MB

YouKnowWhoShortest, 1359B