You are given $N$ positive integers, where $N$ is even. You can arrange them in any order, to maximise the value of the following expression

$pow(A_1,A_2)+pow(A_3,A_4)+\dots +pow(A_{N-1},A_N)$

where $pow(a,b)$ means $a^b \ \%\ b$.

Find the maximum value possible.

INPUT:

• First line contains a single integer $N$, which is even
• Second line contains $N$ positive integers

OUTPUT

• Print a single integer, the maximum value possible

CONSTRAINTS

• $2\le N\le18$
• $1\le A_i\le10^9$