Our teacher is, as usual, late for the first lesson... Of course, someone opened the classroom, but the resentment towards the teacher, who keeps repeating his mistakes, is only growing. It's time to teach our teacher a lesson!
Suddenly, someone had the idea to rummage through the closet. There turned out to be $$$n$$$ sticks from a broken cross, gifted for the New Year. To scare and punish the culprit, something terrifying needs to be created—a non-degenerate triangle$$$^{\text{∗}}$$$ with a huge perimeter!
Since doing this manually is difficult, help us understand what the maximum perimeter of a triangle can be obtained, or $$$-1$$$ if it is impossible to form any triangle. Two sticks cannot form one side. That is, for example, with sticks $$$1,1,2,2$$$, it is not possible to make a triangle with sides $$$2$$$, $$$2$$$, and $$$1+1$$$.
$$$^{\text{∗}}$$$A triangle with sides $$$(a,b,c)$$$ is considered non-degenerate if the following system of inequalities holds: $$$ \left\{ \begin{array}{c} a + b \gt c \\ b + c \gt a \\ c + a \gt b \end{array}\right.$$$
The first line of input contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the number of sticks found in the closet.
The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the lengths of the sticks found in the closet.
Output a single line with the maximum perimeter that can be obtained, or $$$-1$$$ if it is impossible to form any triangle.
| № | Additional Constraints | Points | Required Groups | Comment |
| $$$0$$$ | — | — | — | Tests from the statement |
| $$$1$$$ | $$$n \le 200$$$ | $$$39$$$ | — | — |
| $$$2$$$ | $$$n \le 1000$$$ | $$$22$$$ | $$$1$$$ | — |
| $$$3$$$ | — | $$$39$$$ | $$$0-2$$$ | — |
53 6 2 7 4
17
31 2 9
-1
