Election Paradox

문제

In Oddland, the leader of the country is determined by a democratic election.  The country is divided into an odd number of regions, in which each region has an odd number of voters.

There are two (an even number!) political parties in Oddland, and the winning party is the one that wins the most number of regions.  A party wins a region if it receives more votes than the other party in that region.

Under this system, it is possible that the losing party receives more votes than the winning party.  For example, if there are three regions with $1111$, $33$, and $33$ people, respectively, then a party could receive $88$, $11$, and $11$ votes and lose the election.  In this case, the losing party received the majority of the votes in the total population.

Determine the largest number of votes a party can receive and still lose the election.

입력

The first line of input contains an odd integer $NN$ ($3\le N\le 9993\; \backslash leq\; N\; \backslash leq\; 999$), which is the number of regions in Oddland. 

The next line contains $NN$ odd integers $p_{i}p\_i$ ($1\le p_i\le 9991\; \backslash leq\; p\_i\; \backslash leq\; 999$), which are the populations of the $NN$ cities.

출력

Display the largest number of votes a party can receive and still lose the election.

3
11 3 3

13