Migrated from Lutece 40 Vote

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

美国大选是按各州的投票结果来确定最终的结果的，如果得到超过一半的州的支持就可以当选，而每个州的投票结果又是由该州选民投票产生的，如果某个州超过一半的选民支持希拉里，则她将赢得该州的支持。现在给出每个州的选民人数，请问希拉里至少需要赢得多少选民的支持才能当选？

Input

多组输入数据。

每组数据的第一行包括一个整数$N$($1\leq N\leq 101$）,表示美国的州数，$N=0$表示输入结束。

接下来一行包括$N$个正整数，分别表示每个州的选民数，每个州的选民数不超过$100$。

Output

对于每组数据输出一行，表示希拉里至少需要赢得支持的选民数。

Samples

3
5 7 5
0

6

Resources

电子科技大学第六届ACM程序设计大赛 决赛