409697: GYM103687 L Candy Machine

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Candy Machinetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

JB loves candy very much.

One day, he finds a candy machine with $$$N$$$ candies in it. After reading the instructions of the machine, he knows that he can choose a subset of the $$$N$$$ candies. Each candy has a sweet value. After JB chooses the subset, suppose the average sweet value of the chosen candies is $$$X$$$, all the candies with sweet value strictly larger than $$$X$$$ will belong to JB. After JB makes the choice, the machine will disappear, so JB only has one opportunity to make a choice.

JB doesn't care how sweet the candies are, so he just wants to make a choice to maximize the number of candies he will get. JB has been fascinated by candy and can't think, so he needs you to help him.

Input

The first line contains one integer $$$N$$$ ($$$1\leq N\leq 10^6$$$), denoting the number of candies in the machine.

The second line contains $$$N$$$ integers $$$a_1,a_2,\dots,a_N$$$ ($$$1\leq a_i\leq 10^9$$$), denoting the sweet values of the candies.

Output

One integer, denoting the maximum number of candies JB can get.

ExampleInput
5
1 2 3 4 5
Output
2

加入题单

上一题 下一题 算法标签: