e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, II Stage, II Round

C. Піраміда

У Віталія є n коробок, вага $i$-ої коробки дорівнює $a_i$ кг. Він хоче зібрати з них піраміду. На кожну коробку можна положити рівно одну іншу коробку, проте на цій іншій теж може стояти коробка, і так далі. Також має виконуватися обмеження~--- для кожної коробки її вага має бути принаймні удвічі більша ніж вага усіх коробок, які знаходяться на ній. Знайдіть максимальну кількість коробок, які можуть бути в одній пірамідці. \InputFile Перший рядок містить одне ціле число $n$ ($1 \le n \le 10^5 $) --- кількість коробок. Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) --- ваги коробок. \OutputFile Виведіть одне ціле число~--- максимальну кількість коробок, які можуть бути в одній пірамідці. \Note У першому прикладі можна поставити коробку з вагою $1$ на коробку з вагою $2$, бо $1\cdot2 \le 2$ У другому прикладі можна поставити коробку з вагою $1$ на коробку з вагою $2$, бо $1\cdot2 \le 2$. Після цього ці дві можна поставити на коробку з вагою $6$, бо $(1+2)\cdot2 \le 6$ \Scoring Рішення, які працюють правильно для обмежень $1 \le n \le 1\,000$, набиратимуть $30\%$ балів.
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
1 2 5
Output example #1
2
Input example #2
3
2 6 1
Output example #2
3
Author Mykhailo Perekopskyi
Source Ukrainian Olympiad in Informatics 2021, II Stage