Nested Boxes Problem

Little Y has n boxes. The size of the i-th box is \(a_i\), and each \(a_i\) is guaranteed to be a power of 2 (for example, \(1,2,4,8,16,\dots\)). A box of size \(a_i\) has a capacity of \(\frac{a_i}{2}\), meaning it can contain other boxes whose total sizes do not exceed \(\frac{a_i}{2}\). In particular, a box of size \(1\) cannot contain any other box. Moreover, boxes that are placed inside another box can themselves contain other boxes.

The task is to determine the minimum number of boxes that are not contained in any other box when the boxes are nested optimally.

Input Format: The input begins with a line containing an integer \(n\) (\(1\le n\le 10^5\)). The next line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), each of which is a power of 2.

Output Format: Output a single integer: the minimum number of boxes that remain un-nested (i.e. not contained in any other box).

inputFormat

The first line contains an integer \(n\) (\(1\le n\le 10^5\)), representing the number of boxes. The second line contains \(n\) space-separated integers, where each integer is a power of 2, representing the sizes of the boxes.

outputFormat

Print one integer, the minimum number of boxes that are not contained in any other box after nesting them optimally.

sample

3
1 2 4

1