#133Easy

Maximum product

Time: 1 s · Memory: 256 MB

Sorting

Statement

You are given $n$ integers. Choose three of them (at different positions) so that their product is as large as possible.

Input format

The first line contains $n$ ( $3 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^6$ ).

Output format

A single number — the maximum product of three numbers.

Examples

Input

9
3 5 1 7 9 0 9 -3 10

Output

Input

3
-5 -30 -12

Output

-1800

Note

Sort the array. The answer is the larger of two candidates: the product of the three largest numbers, or the product of the two smallest (they may be negative) and the largest. In the second example all numbers are negative: $(-5) \cdot (-12) \cdot (-30) = -1800$ .

The product reaches $10^{18}$ — a 64-bit type is needed.

Source: acmp.ru, problem 224.

Maximum product

Time: 1 s · Memory: 256 MB

Sorting

Statement

You are given $n$ integers. Choose three of them (at different positions) so that their product is as large as possible.

Input format

The first line contains $n$ ( $3 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^6$ ).

Output format

A single number — the maximum product of three numbers.

Examples

Input

9
3 5 1 7 9 0 9 -3 10

Output

Input

3
-5 -30 -12

Output

-1800

Note

The product reaches $10^{18}$ — a 64-bit type is needed.

Source: acmp.ru, problem 224.