cho.sh

Fun box packing

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.

Medium6GreedySortingTwo pointersBinary searchInterviewNo attempts yetTime limit2sMemory limit512 MB

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.

  1. Let VxV_x be the size of box x and VyV_y the size of box y. You can put box x inside box y if Vy≥2VxV_y \ge 2 V_x.
  2. 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≤N≤500 0001 \le N \le 500\,000) that Minho has.

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

Output

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