题目描述

Byteland 国的居民最近一直为议会选举投票。现在，当结果公布的时候，党派不得不决定联合组建政府。

每个党派都会获得议会中的一定席位。联合政府由这些党派中的一部分组成，他们在议会中的席位数之和严格大于总席位数的一半。对于联合政府来说，席位越多越好。

一个过剩的联合政府是指联合政府中的一个党派被移出后，剩余的联合政府在国会中仍有过半数的席位。

请写一个程序能够找到一个在议会中有着最大可能席位数且不过剩的联合政府。

输入格式

标准输出的第一行包含一个整数 $n$，表示参加选举的党派数。党派被从 $1$ 到 $n$ 编号。

第二行包含 $n$ 个非负整数 $a_1,\dots ,a_n$，被一个空格隔开，$a_i$ 是第 $i$ 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 $10^5$ 的正整数。

输出格式

包含一个整数，表示最大可能席位数。

4
1 3 2 4

7

提示

样例解释：选择第二个政党和第四个。

对于全部数据，$1\le n\le 300$。