南山校园传奇人物开始选了，每个学生都可以去投他们心目中的校园传奇人物，当然腼腆的致标是不会参加这类似的事情…当然如：孽角冬、火星怪兽、鲍导、潇洒哥这些角子肯定是学生们争先恐后投票的对象。他们都想自己成为同学们选出来的传奇人物，校园传奇人物只有一个，按票数来决定谁是校园传奇人物，为了避免他们的FANS会因为投自己偶像时跟其他FANS团的发生武装冲突，学校决定进行一点宏观的调控。现在有K个班，只要得到超过半数的班级数支持的人就能成为校园传奇人物，每个班支持的对象内部里又不一样，所以一个班里中只要得到超过半数的人支持，这个班就会去支持大多数人所支持的人。现在告诉你每个班的人数，问X要想成为校园传奇人物，至少要好多人的支持。
举例 ：
例如有3个班，分别有5 , 5 , 7人 ，那么，至少要有6个人支持才能通过。1班 3 人 ， 2 班 3 人，一共6人支持、才有可能当选校园传奇。
输入数据：
第一行 一个正整数 n ,接下来n个数 ，ai - an代表n个班分别的人数。（任意一个班的人数一个小于1000的奇数）
输出数据：
一行 一个正整数 ans，代表最少的人数。
样例：
输入
3
5 7 5
输出
6
数据范围
30% $n \le 30000+X$ (X为极小的奇数)可以认为是1、3、5、7、9
50% $n \le 300000+X$
100% $n \le 2000001$