Triangle Builder

Interview

Time limit2sMemory limit128 MB

Summary

Given N straw lengths, pick three that form a triangle with the largest possible perimeter, or report -1 if none exist.

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

Problem

Sejun has N straws, and their lengths may differ. Choose exactly 3 of them. If those 3 straws can form a triangle, find the maximum possible sum of the three side lengths.

Input

The first line contains the number of straws N. N is a natural number between 3 and 1,000,000 inclusive.

Each of the next N lines contains the length of one straw. Each length is a natural number between 1 and 1,000,000 inclusive.

Output

If a triangle can be formed, output the maximum possible sum of its three side lengths. If no choice of 3 straws can form a triangle, output -1.

Examples4

Example 1
Input
```
3
1
2
3
```
Expected output
```
-1
```
Example 2
Input
```
3
1
2
2
```
Expected output
```
5
```
Example 3
Input
```
6
2
3
2
3
2
4
```
Expected output
```
10
```
Example 4
Input
```
5
4
5
6
7
20
```
Expected output
```
18
```