Description

The residents of Byteland have recently voted in a parliamentary election. Now, as the results are announced, the parties must decide on forming a coalition government.

Each party obtains a certain number of seats in the parliament. A coalition government consists of a subset of these parties whose total number of seats is strictly greater than half of all seats. For a coalition, having more seats is better.

An excessive coalition is one in which, after removing one party from the coalition, the remaining coalition still holds a majority of seats in the parliament.

Write a program to find a coalition with the maximum possible number of seats in the parliament that is not excessive.

Input Format

The first line of standard input contains an integer $n$, the number of parties in the election. The parties are numbered from $1$ to $n$.

The second line contains $n$ non-negative integers $a_1, \dots, a_n$ separated by single spaces, where $a_i$ is the number of seats won by the $i$-th party. You may assume that the total number of seats in the parliament is a positive integer not exceeding $10^5$.

Output Format

Output a single integer: the maximum possible number of seats.

4
1 3 2 4

7

Hint

Sample explanation: choose the second and the fourth party.

Constraints: For all testdata, $1 \le n \le 300$.

Translated by ChatGPT 5