题目描述

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

输入格式

第一行一个整数n(1≤n≤100)，代表州的数量；

第二行n个不大于100的整数，代表每个州的选民数。

输出格式

一个整数，为至少需要赢得支持的选民数。

输入/输出样例

3
5 7 5

6

说明/提示

时间1000ms，内存256MiB