Codah ClubTrain. Submit. Improve.
Sign in
English
#00008D

Alien Party Guests

Mr. Little Z decided to throw a party for all the aliens he had met when he was on vacation to Mars. However, some of the aliens are really short and wouldn't come to the party if there is going to be really tall aliens there


More specifically, an alien A would come to the party if and only if its combined height with each alien B at the party (height of A + height of B) is strictly larger than the height of all the other aliens at the party


Given the list of the heights of all the aliens Mr. Little Z knows, you have to help him find out what is the maximal number of aliens he can invite to the party so that everyone actually comes


Okay, here is the mathematical definition: you are given N numbers, you have to find the maximal number K such that you can pick K numbers from the N given numbers and for every three numbers A, B and [] from those K numbers, it has to be true that A+B>C and A+C>B and B+C>A


InputThe input is read from the standard input. The first line will contain an integer N where (1 <= N <= 400000), N represents the number of aliens Mr. Little Z knows. Each of the next N lines will contain one integer in the range [1, 2000000000] representing the heights of the aliens.

OutputYou should write to the standard input. In one and only line write one integer K representing the maximal number of aliens Mr. Little Z can invite to the party such that everyone comes

Examples:

Input:
[c]8
1
3
2
9
2
4
11
8

Output:
4

Explanation:
Mr. Little Z can invite the aliens with heights 9, 4, 8, 11

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.