P4394 Election

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**.

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 a single integer: the maximum possible number of seats.

Sample explanation: choose the second and the fourth party. Constraints: For all testdata, $ 1 \le n \le 300 $. Translated by ChatGPT 5