Maximum Perimeter Triangle

You are given a collection of sticks with various lengths. Your task is to select three sticks to form a triangle with the maximum possible perimeter. A set of three sticks can form a triangle if and only if the triangle inequality holds: \(a < b + c\), where \(a\) is the longest side among the three, and \(b\) and \(c\) are the other two sides.

If no valid triangle can be formed, output \(-1\).

Note: The input is provided through standard input and the output should be printed to standard output.

inputFormat

The first line of the input contains a single integer \(n\) representing the number of sticks. The second line contains \(n\) space-separated integers, where each integer denotes the length of a stick.

Example:

6
1 2 3 4 5 10

outputFormat

Output a single integer, which is the maximum perimeter of a triangle that can be formed using any three of the given sticks. If no valid triangle can be formed, output \(-1\).

6
1 2 3 4 5 10

12