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.

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Amortized analysis


Solutions:
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()


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))


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()


import sys
from bisect import bisect_left, bisect_right

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)


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)


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 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()


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)))


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)


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')
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)


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)


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))


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()


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
	elif 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))


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)


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))