Maximum Non-Excess Coalition

In the country of Byteland, each political party has been allocated a certain number of seats in the parliament after an election. A coalition government is formed by choosing a subset of these parties such that the sum of their seats is strictly greater than half of the total seats in parliament. However, the coalition must be non-excess – meaning that if any single party is removed from the coalition, the remaining seats are no longer greater than half of the total seats.

Your task is to choose a coalition of parties that is non-excess and has the maximum possible total number of seats. In other words, if the total number of seats in parliament is \(T\) and the coalition seats sum to \(S\) with \(S > T/2\), then for every party with \(a_i\) seats in the coalition, it must hold that

[ S - a_i \leq \frac{T}{2} ]

You are given the number of parties and an array of integers indicating the number of seats each party holds. Determine the maximum possible \(S\) of a non-excess coalition.

Note: A coalition consisting of a single party is valid if that party alone holds more than half of the total seats.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n\)) representing the number of parties. The second line contains \(n\) space-separated integers, where the \(i\)-th integer represents the number of seats \(a_i\) of the \(i\)-th party.

outputFormat

Output a single integer, the maximum total number of seats \(S\) of a non-excess coalition government.

sample

3
10 20 30

50