← 返回题目列表

Codeforces · 372/A

A. 数袋鼠很有趣

中文机器翻译题面 查看原题

有n只有口袋的袋鼠。每只袋鼠都有一个尺寸(整数)。一只袋鼠可以进入另一只袋鼠的口袋,当且仅当持有该袋鼠的袋鼠的体型至少是被持有的袋鼠的体型的两倍。

每只袋鼠最多只能容纳一只袋鼠,被另一只袋鼠容纳的袋鼠不能容纳任何袋鼠。

从外面看不到被另一只袋鼠抱着的袋鼠。请找出一个饲养袋鼠的计划,其中可见的袋鼠数量最少。

输入

第一行包含一个整数 — n (1 ≤ n ≤ 5·105)。接下来的 n 行中的每一行都包含一个整数 si — 第 i 只袋鼠的大小 (1 ≤ si ≤ 105)。

输出

输出一个整数——可见袋鼠的最佳数量。

示例

输入 #1

8
2
5
7
6
9
8
4
2

输出 #1

5

输入 #2

8
9
1
6
2
6
5
8
3

输出 #2

5