买票

题目描述

$n$ 个人去景点游玩，人人都需要买票。如果一个人的年龄小于或等于另一个人的一半，那么这两个人可以形成一个搭档，合买一张票。已知 $n$ 个人的年龄，如何搭档，才能让购票数量达到最少。

输入格式

• 第一行：单个整数 $n$。
• 第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个人的年龄。

输出格式

• 单个整数：表示购买的最少票数。

数据范围

• 对于 $60\%$ 的数据，保证 $1 \leq n \leq 5000$；
• 对于 $80\%$ 的数据，保证 $1 \leq n \leq 100,000$；
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 1,000,000$；
• $1 \leq a_i \leq 10^9$。

样例输入 #1

6
7 8 10 2 5 6

样例输出 #1

4

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布