Find Minimum Possible Size

Given an array arr of n integers, in a single operation, one can choose two indices, i and j, and delete arr[i] from the array if 2 * arr[i] ≤ arr[j]. A particular element can be chosen at most once. Find the minimum possible size of the array after performing the operation any number of times, possibly zero.

Constraints

N/A

Example 1

Input:

arr = [1, 2, 3, 4, 16, 32, 64]

Output:

4

Explanation: • In the first operation, choose 1 and 16 and delete 1 from the array as 2 * 1 ≤ 16. The array becomes [2, 3, 4, 16, 32, 64]. • In the second operation, choose 2 and 32 and delete 2 from the array as 2 * 2 ≤ 32. The array becomes [3, 4, 16, 32, 64]. • In the third operation, choose 4 and 64 and delete 4 from the array as 2 * 4 ≤ 64. The array becomes [3, 16, 32, 64]. Now the only element that has not been chosen is 3. There have to be two elements, arr[i] and arr[j], for a comparison to take place, so no more operations can occur. The minimum possible size of the array is 4. Note that there are multiple ways to achieve 4 elements in the final array after performing the operations.