大鱼吃小鱼

大鱼吃小鱼

题目限制

1000 ms 128 M

题目描述

小Q的家里养殖着一种肉食性的鱼,缺少食物的时候它们还会自相残杀,不过只有一条鱼的体重至少是另一条的两倍时,体重更重的鱼才能吃掉另一条。

小Q想做一个实验,他把鱼两两一组装到入没有食物的鱼缸(如果鱼的数量是奇数则最后一个鱼缸内只有一条鱼),请问要怎么分组最后鱼的总数最少,求出此时鱼的数量。

输入格式

单组测试数据。
第一行包含一个整数n(1≤n≤5e5)。
接下来n行,每行一个整数si,表示第i条鱼的大小 (1≤si≤1e5)。

输出格式

输出一个整数,即实验后鱼数量的最小值。

数据范围

对于45%的数据,1≤N≤20,1≤si≤100
对于65%的数据,1≤N≤1000
对于100%的数据,1≤N≤5e5,1≤si≤1e5

输入样例

input example1:

8
2
5
7
6
9
8
4
2

input example2:

5
1
2
3
4
5

input example3:

3
2
2
1

输出样例

output example1:

5

output example2:

3

output example3:

2

样例解释

假设有8条鱼体重分别是{2,5,7,6,9,8,4,2},那么当分组情况为[2,6] [2,7] [4,8] [5,9]时,前三组大鱼都吃掉了小鱼,最后一组的两条鱼都活了下来,此时所剩鱼的数量最少,为5条

信息

ID
1067
难度
9
分类
(无)
标签
(无)
递交数
3
已通过
1
通过率
33%
上传者