Description

Xiaoming wants to become the president of country Y. The presidential election in Y is determined by the results of each state. If a candidate wins more than half of the states, they are elected. The result of each state is determined by the votes of its citizens: if more than half of the voters in a state support Xiaoming, he wins that state. Given the number of voters in each state, how many voters does Xiaoming need to win at least to become president?

Input Format

The input contains multiple test cases.
Each test case starts with an integer $N$ ($1≤N≤101$), the number of states in country Y. When $N=0$, the input ends.
The next line contains $N$ positive integers, each representing the number of voters in a state. Each state's voter count does not exceed $100$.

Output Format

For each test case, output a line indicating the minimum number of voters Xiaoming needs to win to become president.

Sample

3
5 7 5
0

6