Slimes

0

0 votes
Easy
Problem

Ashish found N slimes.Each has a fixed shape and size.The shape ans size of i-th slime can be represented by i,Ai.Every slime can absorb another slime whose size is at most twice the size of itself. When a slime of size and shape Y absorbs another slime of size Z and shape W (Z≤2×X), they will merge into one slime of size X+Z and shape Y. Here, depending on the sizes of two slimes, it is possible that both of them can absorb the other.

Ashish has been watching these slimes merge over and over and ultimately become one slime. Find the number of the possible shapes of this slime.

Note : Slime means an unpleasantly thick and slippery liquid substance.

INPUT 
First line contains integer N,number of slimes

Second line contains N integers represening size of each slime.

OUTPUT

Print the number of the possible shapes of the last remaining slime after the N slimes repeatedly merge and ultimately become one slime.

CONSTRAINTS

1<=N<=100000

1<=Ai<=109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The possible shapes of the last remaining slime are shapes 1 and 3. For example, when the slime of color 3 absorbs the slime of shape 2, then the slime of shape 1 absorbs the slime of shape 3, the shape of the last remaining slime will be shape 1.

Editor Image

?