Constructor

On her first birthday, Maggie Simpson, a character from the animated series "The Simpsons," received a construction set as a gift. This playset consists of sticks of various lengths. The ends of these sticks can be joined, and the sticks connected in this way can form any non-zero angle except a straight angle (180°).

Maggie wants to assemble a convex polygon using the maximum number of sticks from the construction set as the sides of this polygon.

Write a program that, given the lengths of the sticks in the construction set, determines whether Maggie can form a convex polygon with the sticks, and if possible, finds the maximum number of sticks she can use for this purpose.

Input

The first line specifies the number $N$ ($2\le N\le 10^5$) of sticks in the set. The second line contains $N$ natural numbers, each less than $10^9$ (not necessarily distinct) - the lengths of the sticks.

Output

Output a single number - the maximum number of sticks from the set that can be used to form a convex polygon, or the number $0$ if forming a convex polygon is not possible.

Examples