Fun box packing

Interview

Time limit2sMemory limit512 MB

Summary

Given N box sizes, nest a box inside another when the outer size is at least twice the inner, each box holds at most one, and minimize the number of visible (unnested) boxes.

Level: Medium6 of 10
Topics: Greedy, Sorting, Two pointers, Binary search
Solved: No attempts yet

Problem

Minho has N boxes. The pile grew too large, so he wants to tidy it up, but he finds ordinary tidying dull and set two rules to make it more fun.

Let $V_x$ be the size of box x and $V_y$ the size of box y. You can put box x inside box y if $V_y \ge 2 V_x$ .
If box x is inside box y, then box y cannot be put inside another box. A box holds at most one other box.

Only a box that is not inside another box is visible. Tidy the boxes under these rules so that the number of visible boxes is as small as possible, and report that minimum.

Input

The first line contains the number of boxes N ( $1 \le N \le 500\,000$ ) that Minho has.

Each of the next N lines contains one box size V ( $1 \le V \le 100\,000$ ).

Output

Print the smallest possible number of visible boxes on one line.

Examples4

Example 1
Input
```
8
2
5
7
6
9
8
4
2
```
Expected output
```
5
```
Example 2
Input
```
8
9
1
6
2
6
5
8
3
```
Expected output
```
5
```
Example 3
Input
```
1
1
```
Expected output
```
1
```
Example 4
Input
```
2
3
5
```
Expected output
```
2
```