在奇数国（Oddland），国家的领导人由民主选举产生。该国被划分为奇数个地区，每个地区都有奇数个选民。
奇数国有两个（偶数个！）政党，赢得最多地区选票的政党获胜。如果一个政党在某个地区获得的票数多于另一个政党，则该政党赢得该地区。
在这种制度下，失败的政党有可能获得比获胜政党更多的总票数。例如，如果有三个地区，人口分别为 11、3 和 3，那么一个政党可能分别获得 8、1 和 1 票，从而输掉选举。在这种情况下，失败的政党在总人口中获得了多数票。
请确定一个政党在输掉选举的情况下，最多能获得的票数。
输入格式
第一行包含一个奇数 $N$ ($3 \le N \le 999$)，表示奇数国的地区数量。
下一行包含 $N$ 个奇数 $p_i$ ($1 \le p_i \le 999$)，表示这 $N$ 个城市的人口。
输出格式
输出一个政党在输掉选举的情况下，最多能获得的票数。
样例
样例输入 1
3 11 3 3
样例输出 1
13