有一些动物有着不同的力量等级，它们正在同一个水坑喝水。在水坑边的动物越多，每只动物能喝到的水就越少。因此，一些动物会试图强迫其他动物离开。

周期性地，群体中最弱的动物可能会受到一些较强动物的攻击。其他动物可能会前来帮助这只最弱的动物。如果攻击者的力量等级之和严格大于防守者的力量等级之和，那么最弱的动物就会离开。其余的防守者（如果有的话）将留下来。这个过程可以重复任意多次。

作为一名初出茅庐的动物学家，你有兴趣确定这些动物是否是逻辑思考者。你拥有大量数据，因此你将编写一个程序来帮助检查在每种情况下，动物们的行为是否达到了最优。每只动物都希望在不被淘汰的前提下，尽可能多地淘汰其他动物。

给定每只动物的力量等级，并假设每只动物总是为了自身利益做出最佳决策，请确定在所有攻击行为结束后，保证能留下的动物数量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示动物的数量。

接下来的 $n$ 行，每行包含一个整数 $s$ ($1 \le s \le 10^9$)。这些是动物的力量等级。任意两只动物的力量等级均不相同。

输出格式

输出一个整数，表示保证能留下的动物数量。

样例

输入 1

4
3
4
8
9

输出 1

3

输入 2

8
20
1
2
13
9
5
8
61

输出 2

1