Layoffs
Because of the hardships the company has been facing recently, they ask you to help them optimize the staff. The company owners would like to only keep the employees who receive a relatively similar salary in a way that after the layoffs, the person earning the most would get at most twice the salary of the person earning the least.
You’d like to make sure the company keeps as much of its staff as possible. So, you start working on the problem right away.
Input
The first line of the input contains a single integer
n (2 ≤ n ≤ ) the number of employees.The next line contain
n space-separated integers (1 ≤ ≤ ) the salaries of the employees.Output
The program should print the maximum number of employees it would be possible to keep.
Examples
Input | Output |
4
4 3 2 4 | 4 |
6
5 4 3 3 7 8 | 4 |
Explanation
- In the first example, it would be possible to keep all the employees. The minimum and maximum will be
2,4, and .
- In the second example, the company could keep the employees with salaries
5 4 3 3or5 4 7 8. In both cases, there will be 4 employees left after the layoffs.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB