题目限制

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条