Description

ZK要从N个团体中选出一些，组成一个ZK内阁，每个团体人数不同. 现在希望你找出一种方案，你选中的团体的人数之和要大于总数的一半，并且ZK内阁的人数越多越好. 对于一个ZK内阁，如果某个团体退出后，其它团体的人数之和仍大于总数的一半，则这个团体被称为是多余的，这是不允许的. 即： 我们选择的人数总数>原来的人数总数的一半（向下取整） 我们选择的人数总数-我们选择的人数最少的团体的人数≤原来的人数总数的一半（向下取整）

Input

第一行给出有多少个团体$N$.

下面给出$N$个正整数，第$i$个整数代表团体$i$的人数。

Output

你的组阁方案中最多可以有多少人.

Samples

4
1 3 2 4

7
//选择第二个团体和第四个

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 300$，$0 \leq 所有团体人数之和 \leq 10^5$。