ボックスを隠す
与えられた
n 個のボックスについて、できるだけ多くのボックスを他のボックスの中に隠したいと考えます。以下のルールに従って配置を行ってください:- 大きいボックスが小さいボックスの少なくとも 2 倍の大きさである場合にのみ、その大きいボックスの中に小さいボックスを入れることができます。
- 1 つのボックスに入れられるのは 1 個だけです（同じボックスに 2 個以上は入れられません）。
最終的に外から見えるボックスの数の最小値はどれだけ小さくできるでしょうか？
入力
入力の最初の行には、ボックスの個数を表す単一の整数
n (1 ≤ n ≤ ) が与えられます。次の行には、各ボックスの大きさを表す
n 個の整数 (1 ≤ ≤ ) が空白区切りで与えられます。出力
最終的に考えられる可視ボックスの最小数を出力してください。
例
Input | Output |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
解説
- 7 5 2 6 4 8 9 2 → (2, 5) (2, 6) (7) (4, 8) (9)
- 3 1 8 2 6 5 6 9 → 1 2 3 5 6 6 8 9 → (1, 5) (2, 6) (3, 6) (8) (9)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB