fb pixel

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.
notion image
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

  1. In the first example, it would be possible to keep all the employees. The minimum and maximum will be 2, 4, and .
  1. In the second example, the company could keep the employees with salaries 5 4 3 3 or 5 4 7 8. In both cases, there will be 4 employees left after the layoffs.
 
To check your solution you need to sign in
Sign in to continue