【题目描述】

在奥德兰，国家领导人由民主选举决定。这个国家被划分为奇数个地区，每个地区都有奇数个的选民。

奥德兰有两个（偶数！）政党，获胜的政党是赢得最多地区的政党。如果一个政党获得的选票比该地区的另一个政党多，那么它就赢得了该地区。

在这种制度下，失败的一方可能比获胜的一方获得更多的选票。例如，如果有三个地区分别有11人、3人和3人，那么一个政党可能会获得8票、1票和1票，并输掉选举。在这种情况下，落败的一方获得了总人口中的大多数选票。

请确定一个政党在输掉选举的情况下能获得的最大票数。

【输入】

第一行输入包含一个奇数整数N（3≤N≤999），这是奥德兰的区域数。

下一行包含N个奇数整数pi（1≤pi≤999），它们是N个城市的人口。

【输出】

输出一个政党在输掉选举的情况下能获得的最大票数。

【样本输入1】

3

11 3 3

【样本输出1】

13