Making a Rectangle

Time limit2sMemory limit256 MB

Summary

Given up to 16 sticks, choose four disjoint groups forming two equal-length pairs of sides to maximize the rectangle's area, or return -1 if impossible.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming, Brute force, Combinatorics
Solved: No attempts yet

Problem

You are given N sticks. You want to choose some of them and connect them to make a rectangle.

Sticks may be connected end to end, but a stick cannot be cut. It is allowed to leave some sticks unused. The two opposite sides of the rectangle must have equal lengths.

Find the largest possible area of a rectangle that can be made. If no rectangle can be made, output -1.

Input

The first line contains the number of sticks N. N is a natural number with 4 <= N <= 16.

The second line contains the stick lengths separated by spaces. Each stick length is a natural number not greater than 10.

Output

Print the largest possible rectangle area on the first line. If it is impossible to make a rectangle with the given sticks, print -1.

Examples6

Example 1
Input
```
6
1 3 3 4 5 7
```
Expected output
```
15
```
Example 2
Input
```
6
9 9 5 6 2 10
```
Expected output
```
-1
```
Example 3
Input
```
7
3 4 7 8 10 2 9
```
Expected output
```
70
```
Example 4
Input
```
9
9 2 7 9 4 9 7 10 3
```
Expected output
```
224
```

Example 5

Input

16
9 9 10 7 7 8 7 5 8 6 9 7 7 10 9 6

Expected output

Example 6
Input
```
13
2 6 4 10 2 8 1 8 2 1 4 8 10
```
Expected output
```
272
```