MultiMax

Time limit1sMemory limit512 MB

Summary

Given n cards with values in [-1000, 1000], pick two or three so their product is maximized.

Level: Medium4 of 10
Topics: Sorting, Greedy, Brute force
Solved: No attempts yet

Problem

There are n cards, and each card has one integer written on it. Two or more cards can carry the same integer. You pick two or three of these cards so that the product of the numbers on the picked cards is as large as possible.

For example, take 6 cards holding 5, 10, -2, 3, 5, and 2. Picking 5, 10, and 5 gives the product 250, and no other choice of two or three cards gives more. With 4 cards holding 10, 0, -5, and 2, picking 10 and 2 gives the product 20, which is the largest.

Given the n numbers written on the cards, write a program that computes the largest product obtainable from two or three cards.

Input

The first line contains the number of cards n. (3 ≤ n ≤ 10,000)

The second line contains the n integers written on the cards, separated by spaces. Each integer is between -1,000 and 1,000 inclusive.

Output

Print the largest product on the first line.

Examples2

Example 1
Input
```
6
5 10 -2 3 5 2
```
Expected output
```
250
```
Example 2
Input
```
4
10 0 -5 2
```
Expected output
```
20
```