One day Vasya was on a physics practical, performing the task on measuring the capacitance. He followed the teacher's advice and did as much as n measurements, and recorded the results in the notebook. After that he was about to show the results to the teacher, but he remembered that at the last lesson, the teacher had made his friend Petya redo the experiment because the largest and the smallest results differed by more than two times. Vasya is lazy, and he does not want to redo the experiment. He wants to do the task and go home play computer games. So he decided to cheat: before Vasya shows the measurements to the teacher, he will erase some of them, so as to make the largest and the smallest results of the remaining measurements differ in no more than two times. In other words, if the remaining measurements have the smallest result x, and the largest result y, then the inequality y ≤ 2·x must fulfill. Of course, to avoid the teacher's suspicion, Vasya wants to remove as few measurement results as possible from his notes.

Help Vasya, find what minimum number of measurement results he will have to erase from his notes so that the largest and the smallest of the remaining results of the measurements differed in no more than two times.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 10^5) — the number of measurements Vasya made. The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 5000) — the results of the measurements. The numbers on the second line are separated by single spaces.


-----Output-----

Print a single integer — the minimum number of results Vasya will have to remove.


-----Examples-----
Input
6
4 5 3 8 3 7

Output
2

Input
4
4 3 2 4

Output
0



-----Note-----

In the first sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.

Difficulty: interview

Starter code:

Solutions:
import sys
from bisect import *
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
ans=n=int(input())
a=sorted(map(int,sys.stdin.readline().split()))
for i in range(n):ans=min(ans,n-bisect_right(a,a[i]*2)+i)
print(ans)

import sys

sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

n = int(input())
t = list(map(int,sys.stdin.readline().split()))
p = [0] * 5001
for i in t:
    p[i] += 1
q = p[:]
for i in range(1, 5001):
    q[i] += q[i - 1]
ans = q[5000] - q[2499]
for i in range(1, 2501):
    if p[i]:
        s = q[2 * i] - q[i - 1]
        if s > ans: ans = s
print(n - ans)

f = open('input.txt', 'r')
n = int(f.readline())
c = sorted(map(int, f.readline().split()))
j, v = 0, n - 1
for i in range(n):
    while j < n - 1 and 2 * c[i] >= c[j + 1]:
        j += 1
    v = min(v, n + i - j - 1)
open('output.txt', 'w').write(str(v))

import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
res = [int(t) for t in input().split()]
res.sort()
min_erase = n
i, j = 0, 0
while i != n - 1:
    if res[j] <= 2 * res[i]:
        ans = True
        if n - (j - i + 1) < min_erase:
            min_erase = n - (j - i + 1)
    else:
        ans = False
    if ans and j != n - 1:
        j += 1
    else:
        i += 1
print(min_erase)


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
res = [int(t) for t in input().split()]
res.sort()
min_erase = n
i, j = 0, 0
while i != n - 1:
    if res[j] <= 2 * res[i]:
        ans = True
        if n - (j - i + 1) < min_erase:
            min_erase = n - (j - i + 1)
    else:
        ans = False
    if ans and j != n - 1:
        j += 1
    else:
        i += 1
print(min_erase)


def main():
    import sys
    from bisect import bisect
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
    n = int(input())
    cc = sorted(map(int, input().split()))
    print(n - max(bisect(cc, c * 2, i) - i for i, c in enumerate(cc)))


def __starting_point():
    main()

__starting_point()

def main():
    import sys
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
    n, res, j = int(input()), [], 0
    cc, f = sorted(map(int, input().split())), res.append
    for i, c in enumerate(cc):
        while cc[j] * 2 < c:
            j += 1
        f(i - j)
    print(n - max(res) - 1)


def __starting_point():
    main()

__starting_point()

import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
import bisect
def find_ge(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a):
        return i
n = int(input())
array = sorted([int(i) for i in input().split()])
double = [2*i for i in array]
minimum = n
for i in range(n-1, -1, -1):
    minimum = min(n - 1 - i + find_ge(double, array[i]), minimum)
print(minimum)

f = open('input.txt', 'r')

n = int(f.readline())

c = sorted(map(int, f.readline().split()))

j, v = 0, n - 1

for i in range(n):

    while j < n - 1 and 2 * c[i] >= c[j + 1]:

        j += 1

    v = min(v, n + i - j - 1)

open('output.txt', 'w').write(str(v))



# Made By Mostafa_Khaled


import bisect
def physics(f):
        num = int(file.readline())
        res = list(map(int,file.readline().split()))
        res.sort()
        y = res[num-1]
        x = res[0]
        m = num
        if y <= 2*x:
               return 0
        else:
          for index,x in enumerate(res):
             y = 2*x
             i = bisect.bisect(res,y,index+1,num)
             
             if res[i-1] <= 2*x:   
                     removes = (index + num - i)
                     m = min(m,removes)
             if index >= m:
                    return m
        

file = open('input.txt', 'r')
open('output.txt', 'w').write(str(physics(file)))


f = open('input.txt', 'r')
n = int(f.readline())
c = sorted(map(int, f.readline().split()))
j, v = 0, n - 1
for i in range(n):
    while j < n - 1 and 2 * c[i] >= c[j + 1]:
        j += 1
    v = min(v, n + i - j - 1)
open('output.txt', 'w').write(str(v))


import sys
sys.stdin = open('input.txt')
sys.stdout = open('output.txt','+w')

n = int(input())
a = [0] + sorted(list(map(int, input().split())))

start = 1
res = 0
for end in range(1,n+1):
	while(a[end] > 2*a[start]):
		start += 1
	res = max(res, end - start + 1)
print(n - res)

import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
from bisect import bisect_right as br

l = I() + [MOD]

l.sort()
ans = MOD
for i in range(n):
	k = l[i]
	j = br(l, 2*l[i])
	ans = min(ans, n - (j - i))
print(ans)

import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
from bisect import bisect_right as br

l = I()

l.sort()
ans = MOD
for i in range(n):
	k = l[i]
	j = br(l, 2*l[i])
	ans = min(ans, n - (j - i))
print(ans)

f=open("input.txt","r")
f1=open("output.txt","w")
def search(mas,val):
    p=0
    ost = len(mas) - 1
    while (p <= ost):
        mid = (p + ost) // 2;
        if mas[mid] > val*2:
            ost = mid - 1;
        else :
            p = mid + 1;
                

            
    return p;
n=int(f.readline())
ma=n-1
l=list(map(int,f.readline().split()))
l=sorted(l)

for i in range(n) :
    e=search(l,l[i])
    
    w=i+n-e
    ma=min(ma,w)
ma=str(ma)
f1.write(ma)
f.close()
f1.close()
    


def solve(seq):
    n = len(seq)
    cnt = [0] * 5001
    for e in seq:
        cnt[e] += 1

    acc = [0]
    for i in range(1, 5001):
        acc.append(acc[-1] + cnt[i])

    ans = n
    for i in range(5001):
        if cnt[i] > 0:
            if 2 * i < 5001:
                n2remove = n - acc[2*i] + acc[i-1]
            else:
                n2remove = n - acc[-1] + acc[i-1]
            ans = min(ans, n2remove)

    return ans


def main():
    with open('input.txt') as f:
        _ = int(f.readline())
        seq = list(map(int, f.readline().split()))

    ans = solve(seq)

    with open('output.txt', 'w') as f:
        f.write(str(ans))


def __starting_point():
    main()

__starting_point()

def solve(seq):
    n = len(seq)
    cnt = [0] * 5001
    for e in seq:
        cnt[e] += 1

    acc = [0]
    for i in range(1, 5001):
        acc.append(acc[-1] + cnt[i])

    ans = n
    for i in range(5001):
        if cnt[i] > 0:
            n2remove = n - acc[min(2*i, 5000)] + acc[i-1]
            ans = min(ans, n2remove)

    return ans


def main():
    with open('input.txt') as f:
        _ = int(f.readline())
        seq = list(map(int, f.readline().split()))

    ans = solve(seq)

    with open('output.txt', 'w') as f:
        f.write(str(ans))


def __starting_point():
    main()

__starting_point()

with open('input.txt') as f:
    n = int(f.readline())
    arr = list(map(int, f.readline().split()))
mark = [0 for _ in range(5001)]
sumMark = [0 for _ in range(5001)]
total = 0
minA = 1000000
for v in arr:
    mark[v] += 1
    total+=1
for i in range(1,5001):
    if mark[i]>0:
        sumMark[i] = sumMark[i-1]+mark[i]
    else:
        sumMark[i] = sumMark[i-1]
for i in range(1,5001):
    if i <=2500:
        if mark[i] >0:
            preValue = sumMark[i-1]
            postValue = total-sumMark[i*2]
            remove = postValue +preValue
            ret = total-remove
            if remove<minA:
                minA = remove
    else:
        if mark[i] >0:
            remove = sumMark[i-1]
            ret = total-remove
            if remove<minA:
                minA = remove
with open('output.txt', 'w') as f:
    f.write(str(minA))

from bisect import bisect_right
R = lambda: map(int, input().split())
f = open("input.txt","r")
n = int(f.readline())
L = sorted(map(int, f.readline().split()))
res = 10**9
for i in range(n):
    k = bisect_right(L,2*L[i])
    if k == n:
        res = min(res,i)
        break
    res = min(res,i+n-k)
open('output.txt', 'w').write(str(res))

f = open('input.txt', 'r')
n = int(f.readline())
arr = sorted(map(int, f.readline().split()))
j, res = 0, n - 1
for i in range(n):
    while j < n - 1 and 2 * arr[i] >= arr[j + 1]: j += 1
    res = min(res, n + i - j - 1)
open('output.txt', 'w').write(str(res))


f = open('input.txt', 'r')
n = int(f.readline())
arr = sorted(map(int, f.readline().split()))
j = 0
res = n - 1

for i in range(n):
    while j < n - 1 and 2 * arr[i] >= arr[j + 1]:
        j += 1
    res = min(res, n + i - j - 1)


open('output.txt', 'w').write(str(res))


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
from bisect import bisect_right as br

l = I()

l.sort()
ans = MOD
for i in range(n):
	k = l[i]
	j = br(l, 2*l[i])
	ans = min(ans, n - (j - i))
print(ans)


class CodeforcesTask253BSolution:
    def __init__(self):
        self.result = ''
        self.measure_count = 0
        self.measurements = []

    def read_input(self):
        in_ = open("input.txt", "r").read().split("\n")
        self.measure_count = int(in_[0])
        self.measurements = [int(x) for x in in_[1].split(" ")]

    def process_task(self):
        occurs = [0 for x in range(5000)]
        for m in self.measurements:
            occurs[m - 1] += 1
        dels = [sum(occurs[:m-1]) + sum(occurs[m * 2:]) for m in range(1, 5000)]
        self.result = str(min(dels))

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask253BSolution()
    Solution.read_input()
    Solution.process_task()
    open("output.txt", "w").write(Solution.get_result())

__starting_point()

#   In this template you are not required to write code in main
import sys
# inf = float("inf")
# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod,MOD=1000000007,998244353
# vow=['a','e','i','o','u']
# dx,dy=[-1,1,0,0],[0,0,1,-1]
#sys.setrecursionlimit(1000000)
#from cmath import sqrt
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import ceil,floor,log,sqrt,factorial,pow,pi,gcd
from bisect import bisect_left,bisect_right
#import numpy as np
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()

sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

n=int(input())
arr=get_array()
arr.sort()
maxi=-1
for i in range(n):
    x=bisect_right(arr,2*arr[i])
    x-=1
    maxi=max(maxi,x-i+1)
print(n-maxi)


fd = open("input.txt","r")
fd1 = open("output.txt","w")
n = int(fd.readline())
arr = list(map(int,fd.readline().split()))
freq = [0 for i in range(5001)]
for i in range(n):
	freq[arr[i]]+=1
presum = [0 for i in range(5001)]
for i in range(1,5001):
	presum[i] = presum[i-1]+freq[i]
tot = n
mini = n
for i in range(1,5001):
	maxa = 2*i
	if maxa>5001:
		break
	ans = n-( presum[maxa] - presum[i] + freq[i])
	mini = min(mini,ans)
fd1.write(str(mini))