There are n kangaroos with pockets. Each kangaroo has a size (integer number). A kangaroo can go into another kangaroo's pocket if and only if the size of kangaroo who hold the kangaroo is at least twice as large as the size of kangaroo who is held.

Each kangaroo can hold at most one kangaroo, and the kangaroo who is held by another kangaroo cannot hold any kangaroos.

The kangaroo who is held by another kangaroo cannot be visible from outside. Please, find a plan of holding kangaroos with the minimal number of kangaroos who is visible.


-----Input-----

The first line contains a single integer — n (1 ≤ n ≤ 5·10^5). Each of the next n lines contains an integer s_{i} — the size of the i-th kangaroo (1 ≤ s_{i} ≤ 10^5).


-----Output-----

Output a single integer — the optimal number of visible kangaroos.


-----Examples-----
Input
8
2
5
7
6
9
8
4
2

Output
5

Input
8
9
1
6
2
6
5
8
3

Output
5

Difficulty: competition

Starter code:

Solutions:
# -*- coding: utf-8 -*-
from time import perf_counter
from sys import stdin

def run(n, s):
    m = 0
    small = n // 2
    for big in range(n-1, (n+1)//2-1, -1):
        while small >= 0 and s[small] > s[big] / 2:
            small -= 1
        if small == -1:
            break
        #print(small, big)
        small -= 1
        m += 1
    print(n-m)

def run2(n, s):
    r = n - 1
    l = n // 2 - 1
    result = 0
    while l >= 0:
        if s[l] * 2 <= s[r]:
            result += 1
            r -= 1
        l -= 1
    print(n - result)

n = int(input())
s = sorted([int(x) for x in stdin.read().strip().split('\n')])
run(n, s)


# -*- coding: utf-8 -*-
from sys import stdin

def run(n, s):
    m = 0
    small = n // 2
    for big in range(n-1, (n+1)//2-1, -1):
        while small >= 0 and s[small] > s[big] / 2:
            small -= 1
        if small == -1:
            break
        small -= 1
        m += 1
    print(n-m)

n = int(input())
s = sorted([int(x) for x in stdin.read().strip().split('\n')])
run(n, s)


# Тупо скопировал решение, ибо никак не пойму поверить в решение за менее чем 1 #секунду((( 

from sys import stdin

def run(n, s):
    m = 0
    small = n // 2
    for big in range(n-1, (n+1)//2-1, -1):
        while small >= 0 and s[small] > s[big] / 2:
            small -= 1
        if small == -1:
            break
        small -= 1
        m += 1
    print(n-m)

n = int(input())
s = sorted([int(x) for x in stdin.read().strip().split('\n')])
run(n, s)

def main():
    from sys import stdin
    n = int(input())
    l = sorted((list(map(int, stdin.read().splitlines()))), reverse=True)
    ita = iter(enumerate(l))
    i, a = next(ita)
    for b in l[(n + 1) // 2:]:
        if a >= b * 2:
            i, a = next(ita)
    print(n - i)


def __starting_point():
    main()

__starting_point()

import math,sys
n=int(input());k=n
a=sorted([int(x) for x in sys.stdin.read().strip().split('\n')])
p1=math.floor((n-1)/2);p2=n-1
while p1>=0:
    if 2*a[p1]<=a[p2]:
        k-=1;a[p2]=0;p2-=1
    p1-=1
k=max(math.ceil(n/2),k)
sys.stdout.write(str(k))

import math,sys
n=int(input())
a=sorted(list(int(sys.stdin.readline()) for i in range(n)))
mid=math.floor((n-1)/2)
c=0
i=n-1;x=mid;k=n
while x>=0:
    if 2*a[x]<=a[i]:
        k-=1
        i-=1
    x-=1    
k=max(math.ceil(n/2),k)    
sys.stdout.write(str(k))

from sys import stdin, stdout
import math
n=int(input())
a=sorted(list(int(stdin.readline()) for i in range(n)))
mid=math.floor((n-1)/2)
c=0
i=n-1;x=mid;k=n
while x>=0:
    if 2*a[x]<=a[i]:
        k-=1
        i-=1
    x-=1    
k=max(math.ceil(n/2),k)    
stdout.write(str(k))

from sys import stdin, stdout
from math import floor,ceil
n=int(input())
a=sorted(list(int(stdin.readline()) for i in range(n)))
mid=floor((n-1)/2)
c=0
i=n-1;x=mid;k=n
while x>=0:
    if 2*a[x]<=a[i]:
        k-=1
        i-=1
    x-=1    
k=max(ceil(n/2),k)    
stdout.write(str(k))

n=int(input())
a=[]
count1=0;count2=0
from sys import stdin,stdout
for i in range(n):
    a.append(int(stdin.readline()))
a.sort()
while count2!=n//2:
    if a[count1]*2<=a[count2+n//2]:
        count1+=1
        count2+=1
    else:
        count2+=1
stdout.write(str(n-count1))

import sys
import math
n=int(input())
a=sorted(list(int(sys.stdin.readline()) for i in range(n)))
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    if 2*a[i]<=a[j]:
        j-=1
        k+=1
    i-=1
#print(a)
print(n-k)
        


# Made By Mostafa_Khaled 
bot = True 
import math,sys

n=int(input());k=n

a=sorted([int(x) for x in sys.stdin.read().strip().split('\n')])

p1=math.floor((n-1)/2);p2=n-1

while p1>=0:

    if 2*a[p1]<=a[p2]:

        k-=1;a[p2]=0;p2-=1

    p1-=1

k=max(math.ceil(n/2),k)

sys.stdout.write(str(k))

# Made By Mostafa_Khaled


import sys
import math
n=int(input())
a=sorted(int(x) for x in sys.stdin)
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    if 2*a[i]<=a[j]:
        j-=1
        k+=1
    i-=1
#print(a)
print(n-k)

import sys
import math
n=int(input())
a=sorted(int(x) for x in sys.stdin)
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    b = int(2*a[i]<=a[j])
    j-=1*b
    k+=1*b
    i-=1
#print(a)
print(n-k)

import sys
import math
n=int(input())
a=sorted(int(x) for x in sys.stdin)
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    b = int(2*a[i]<=a[j])
    j-=1*b
    k+=1*b
    i-=1
#print(a)
print(n-k)

import sys
import math
n=int(input())
a=sorted(int(x) for x in sys.stdin)
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    b = int(2*a[i]<=a[j])
    j-=1*b
    k+=1*b
    i-=1
#print(a)
print(n-k)

import sys
import math
n=int(input())
a=sorted(int(x) for x in sys.stdin)
i=(n//2)-1
j=n-1
k=0
while j>((n//2)-1) and i>=0:
    if 2*a[i]<=a[j]:
        j-=1
        k+=1
    i-=1
#print(a)
print(n-k)

import sys
import math
n = int(input())
k = sorted(int(x) for x in sys.stdin)
p1 = (n//2)-1
p2 = n-1
count = 0
while p2>(n//2-1) and p1>=0:
    if (k[p1]*2<=k[p2]):
        p2-=1
        count+=1
    p1-=1
print(n-count)


import sys
import math
n = int(input())
k = [int(x) for x in sys.stdin]
size = (5*10**5+4)
r = [0]*size
c = [0]*size
for i in k: 
    r[i//2]+=1 #neu co so = x2 -> +1
    c[i]+=1 #dem so lan xuat hien trong input
t = b = 0
result = n
for i in range(size-1, -1, -1):
    r[i]+=t
    t=r[i]
    if (c[i]>0):
        result-=min(c[i], r[i]-b)
        b+=min(c[i], r[i]-b)
    if (result<=((n+1)//2)):
        break
print(max(result,(n+1)//2))



import sys
import math
n = int(input())
k = [int(x) for x in sys.stdin]
size = (5*10**5+4)
r = [0]*size
c = [0]*size
for i in k: 
    r[i//2]+=1 #neu co so = x2 -> +1
    c[i]+=1 #dem so lan xuat hien trong input
t = b = 0
result = n
for i in range(size-1, -1, -1):
    r[i]+=t
    t=r[i]
    if (c[i]>0):
        result-=min(c[i], r[i]-b)
        b+=min(c[i], r[i]-b)
    if (result<=((n+1)//2)):
        break
print(max(result,(n+1)//2))

import sys

n = int(input())
a = [int(i) for i in sys.stdin]
a.sort()
i = 0
j = n//2
ans=n
while i < n//2 and j < n:
    if 2*a[i] <= a[j]:
        ans-=1
        i+=1
        j+=1
    else:
        j+=1
print(ans)

import sys

def sol(a,n):
    a.sort()
    i = 0
    j = n//2
    ans = n
    while i < n//2 and j < n:
        if 2*a[i] <= a[j]:
            ans-=1
            i+=1
            j+=1
        else:
            j+=1
    return ans

n = int(input())
a = [int(i) for i in sys.stdin]
print(sol(a,n))