← 返回题目列表

Codeforces · 545/D

D. 队列

中文机器翻译题面 查看原题

小女孩Susie和妈妈一起去购物,她想知道如何提高服务质量。

队列中有 n 个人。对于每个人,我们知道为他服务所需的时间。如果一个人等待的时间超过了为他服务所需的时间,他就会感到失望。一个人等待的时间是他前面排队的所有人都得到服务的总时间。苏西认为,如果我们交换队列中的一些人,就可以减少失望的人数。

帮助Susie找出通过交换队列中的人最多可以达到多少个不失望的人。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。

下一行包含 n 个整数 ti (1 ≤ ti ≤ 109),用空格分隔。

输出

打印一个数字——队列中不失望的最大人数。

示例

输入 #1

5
15 2 1 5 3

输出 #1

4

注意

这样的安排就达到了价值4,例如:1,2,3,5,15。这样,你就可以让除了时间为5的人之外的一切都感到不失望。