Problem:
 Score : 400 points    Problem Statement Snuke found N strange creatures.
Each creature has a fixed color and size. The color and size of the i -th creature are represented by i and A_i , respectively.  Every creature can absorb another creature whose size is at most twice the size of itself.
When a creature of size A and color B absorbs another creature of size C and color D ( C \leq 2 \times A ), they will merge into one creature of size A+C and color B .
Here, depending on the sizes of two creatures, it is possible that both of them can absorb the other.  Snuke has been watching these creatures merge over and over and ultimately become one creature.
Find the number of the possible colors of this creature.      Constraints  2 \leq N \leq 100000  1 \leq A_i \leq 10^9  A_i is an integer.         Input The input is given from Standard Input in the following format:  N  A_1  A_2 … A_N       Output Print the number of the possible colors of the last remaining creature after the N creatures repeatedly merge and ultimately become one creature.        Sample Input 1 3
3 1 4      Sample Output 1 2  The possible colors of the last remaining creature are colors 1 and 3 .
For example, when the creature of color 3 absorbs the creature of color 2 , then the creature of color 1 absorbs the creature of color 3 , the color of the last remaining creature will be color 1 .       Sample Input 2 5
1 1 1 1 1      Sample Output 2 5  There may be multiple creatures of the same size.       Sample Input 3 6
40 1 30 2 7 20      Sample Output 3 4

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    A.sort()
    sa = [0]
    for a in A:
        sa.append(sa[-1] + a)

    b = []
    for i in range(N-1):
        if 2*sa[i+1] >= A[i+1]:
            b.append(True)
        else:
            b.append(False)
    b.append(True)

    ans = 0
    for c in b[::-1]:
        if c:
            ans += 1
        else:
            break
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    A.sort()
    sa = [0]
    for a in A:
        sa.append(sa[-1] + a)

    b = []
    for i in range(N-1):
        if 2*sa[i+1] >= A[i+1]:
            b.append(True)
        else:
            b.append(False)
    b.append(True)

    ans = 0
    for c in b[::-1]:
        if c:
            ans += 1
        else:
            break
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n = int(input())

arr = map(int,raw_input().split())
arr.sort()
cs = np.cumsum(arr)

ans = 1

i = n-2
while i > -1 and cs[i] * 2 >= arr[i+1]:
	ans += 1
	i -= 1

print ans

Solution (Python):
n = input()
v = map(int, raw_input().split(' '))
v.sort()

def good(mid, v):
	sum = v[mid]
	for i in range(n):
		if i != mid:
			if v[i] > 2 * sum:
				return False

			sum += v[i]

	return True


l, r = 0, n - 1
best = n - 1

while l <= r:
	mid = (l + r) / 2

	if good(mid, v):
		best = mid
		r = mid - 1
	else:
		l = mid + 1

print n - best

Solution (Python):
import bisect


def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()
    a2 = a[::-1]

    sa = [0 for i in range(n+1)]
    for i in range(1, n+1):
        sa[i] = sa[i-1] + a[i-1]

    ans, max_s = 0, a2[0]
    for i in range(n):
        t = sa[bisect.bisect_right(a, 2*a2[i])]
        if max_s <= 2 * t:
            ans += 1
            max_s = a2[i]
        else:
            break

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = input().split()
for i in range(0,N):
	a[i] = int(a[i])
a.sort()
t = 0
flag = 1
sum_a = 0
for i in range(0,N-1):
	sum_a += a[i]
	if sum_a*2 < a[i+1]:
		t = i+1

			
print(N-t)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

A.sort()

result = 0
t = 0

for a in A:
    if a <= t * 2:
        t += a
        result += 1
    else:
        t += a
        result = 1

print(result)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
c = 0
s = 0
for a in A:
    if a <= s*2:
        c += 1
    else:
        c = 1
    s += a
print(c)

Solution (Python):
from itertools import accumulate

N=int(input())
A=[int(x) for x in input().split()]

A.sort()
S=list(accumulate(A))
S.sort(reverse=True)
A.sort(reverse=True)

ans=1

for i in range(1,N):
  cnt=S[i]
  if S[i]*2 >= A[i-1]:
    ans+=1
  else:
    break

print(ans)

Solution (Python):
import sys

N = int(input())
A = list(map(int,input().split()))
A  = sorted(A)


res = 1
s = sum(A[0:N-1])
i = N - 2
while i >=0:
    if A[i + 1] <= 2 * A[i]:
        res += 1
        s -= A[i]
    else:
        if A[i + 1] <= 2 * s:
            res += 1
            s -= A[i]
        else:
            i = -1
        
    i -= 1
print(res)

Solution (Python):


import sys, math, copy




HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(input())
    an = list(map(int, input().split()))
    an = sorted(an)
    assert len(an) == n
    bn = [an[0]]
    for i in range(1, n):
        bn.append(bn[-1] + an[i])

    cuts = []
    for i in range(n - 1):
        if bn[i] * 2 < an[i + 1]:
            cuts.append(i + 1)

    maxj = max(cuts + [0])
    assert 0 <= maxj < n
    print(n - maxj)

main()

Solution (Python):
n = int(input())
creatures = list(map(int,input().split()))
creatures.sort()
ans = 0
p = creatures[0]
for i in range(1, n):
    if creatures[i] > p * 2:
        ans = 0
    else:
        ans += 1
    p += creatures[i]
ans += 1
print(ans)

Solution (Python):
N = int(input())

A = sorted(list(map(int,input().split())),reverse=True)

min_abs = A[0]
ans = 1
for i in range(1,N):
    if A[i]*2 >= min_abs:
        ans += 1
    elif sum(A[i:])*2 >= min_abs:
        ans += 1
    else:
        break
    min_abs = A[i]
    
print(ans)

Solution (Python):
from copy import deepcopy


def read():
    return int(input())


def readlist():
    return list(map(int, input().split()))

def readmap():
    return map(int, input().split())


N = read()
A = readlist()
A.sort()

Acum = deepcopy(A)

for i in range(1, N):
    Acum[i] += Acum[i-1]

ans = 0
for i in reversed(range(N)):
    if i == N-1:
        ans += 1
    elif 2 * Acum[i] >= A[i+1]:
        ans += 1
    else:
        print(ans)
        quit()
print(N)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()

r=0
b=[]
for i in a:
  r+=i
  b.append(r)
ans=1

  
b.sort(reverse=True)
a.sort(reverse=True)

for i in range(1,n):
  if b[i] * 2 >=a[i-1]:
    ans+=1
  else:
    break

print(ans)

Solution (Python):
from bisect import bisect_left
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
b,c = [a[0]],[False for i in range(n)]
for i in range(1,n): b.append(b[-1]+a[i])
for i in range(n-1,-1,-1):
	x = bisect_left(a,b[i]*2+0.5)
	if x==n: c[i] = True
	elif c[x-1]: c[i] = True
print(sum(c))

Solution (Python):
import sys
import numpy as np

import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(int(input_raw[i]))

    A.sort(reverse = True)
    sum_A = [0 for i in range(N)]
    for i in range(N-1, -1, -1):
        if i == N - 1:
            sum_A[i] = A[i]
        else:
            sum_A[i] = A[i] + sum_A[i + 1]


    count = 1
    for i in range(1, N):
        if 2* sum_A[i] >= A[i - 1]:
            count += 1
        else:
            break;

    print count

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
cumA = [0]
for a in A:
    if a > 2*cumA[-1]:
        t = A.index(a)
    cumA.append(cumA[-1] + a)
print(N-t)

Solution (Python):
import math
N = int(input())
A = sorted(list(map(int, input().split())))

left = 0
right = N
for i in range(int(math.log(N, 2)) + 10):
    center = (left + right) // 2
    B = A[:center] + A[center+1:]
    slime = A[center]

    for b in B:
        if 2*slime >= b:
            slime += b
        else:
            left = center
            break
    else:
        right = center

print(N - right)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
A_SUM = sum(A)
count = 1
for i in A:
    A_SUM -= i
    if 2*A_SUM >= i:
        count += 1
    else:
        break
print(count)

Solution (Python):
N = int(input())
src = list(map(int,input().split()))
src.sort()

k = s = 0
for i,a in enumerate(src):
    if 2*s < a:
        k = i
    s += a
print(N - k)

Solution (Python):
n = int(input())
xs = [int(x) for x in input().split()]
xs.sort()


acc = [0]
for i in range(n):
    acc.append(acc[-1] + xs[i])


ans = 1
for i in range(n-2,-1,-1):
    if acc[i+1] * 2 >= xs[i+1]:
        ans += 1
    else: break
print(ans)

Solution (Python):
n = int(raw_input())

v = map(int, raw_input().split(' '))
v.sort()

sum = 0

res = n

for i in range(n):
	if 2 * sum < v[i]:
		res = n - i
	sum += v[i]
	
print res

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
m = [[a for i in range(2)] for j in range(n)]
sum=0
count=1
a.sort()
for i in range(n):
 m[i][0]=a[n-i-1]
 sum=sum+a[i]
 m[n-i-1][1]=sum

for i in range(n-1):
  if 2*m[i+1][1]>=m[i][0]:
     count=count+1
  else:
     break

print(count)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")

def ok(idx, a_list):
    now = a_list[idx]
    for i in range(len(a_list)):
        if i == idx:
            continue
        else:
            if a_list[i] > now * 2:
                return False
            now += a_list[i]
    return True


def main():
    N = int(input())
    a_list = sorted(list(map(int, input().split())))

    
    low, high, ans = -1, N, -1
    while high - low > 1:
        middle = (low + high) // 2
        if ok(middle, a_list):
            ans = middle
            high = middle
        else:
            low = middle

    print(N - ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,a=int(input()),sorted(list(map(int,input().split())))
lb,ub=-1,n
def check(mid):
	sz=a[mid]
	for i in range(n):
		if i==mid: continue
		if 2*sz>=a[i]: 
			sz+=a[i]
		else:
			return False
	return True
while ub-lb>1:
	mid=(lb+ub)//2
	if check(mid):
		ub=mid
	else:
		lb=mid
print(n-ub)

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
a.sort()
s = [0] * (n + 1)
for i in xrange(n):
    s[i + 1] += s[i] + a[i]
for i in xrange(n, 0, -1):
    if 2 * s[i - 1]  < a[i - 1]:break
print n - (i - 1)

Solution (Python):
n = int(input())
creature_states = list(map(int, input().split()))
creature_states.sort()

count = 0
total_size = creature_states[0]

for i in range(1, n):
  if creature_states[i] <= total_size * 2:
    count += 1
  else:
    count = 0
  total_size += creature_states[i]

print(count + 1)

Solution (Python):
n = int(raw_input())
l = map(int, raw_input().split())
l.sort()
l.reverse()
s = sum(l)
cnt = 1
for v in l:
    s -= v
    if v <= s*2:
        cnt += 1
    else:
        break
print cnt

Solution (Python):
n = input()
arr = map(int, raw_input().split())
arr.sort()

res = 0
cur = 0
for i in xrange(len(arr) - 1):
	cur += arr[i]
	res += 1
	if not (arr[i+1] <=  2 * cur):
		res = 0

print res + 1

Solution (Python):
def smallestPossible(creatures):
	creatureSum = 0
	possible = 0
	for i in range(len(creatures)):
		if i == len(creatures) - 1:
			return possible + 1
		creatureSum += creatures[i]
		if (2 * creatureSum >= creatures[i + 1]):
			possible += 1
		else:
			possible = 0

input()
print(smallestPossible(sorted(list(map(lambda x: int(x), input().split())))))

Solution (Python):


N = int(input())
A = list(map(int, input().split()))
A.sort()
sumA=sum(A)


cnum = 1
for i in range(N-1,0,-1):
    sumA -= A[i]
    if sumA * 2 < A[i]:
        break
    else:
        cnum += 1
print(cnum)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split(' ')]

a.sort()
s = [a[0]]
for i in range(1, n):
  s.append(s[i - 1] + a[i])

res = 1
for i in reversed(range(0, n - 1)):
  if s[i] * 2 >= a[i + 1]:
    res += 1
  else:
    break

print(res)

Solution (Python):
N = int(input())

size_list = [int(i) for i in input().split()]
size_list.sort(reverse=True)

cnt = 1
compare = sum(size_list)

for i in range(N):
    compare -= size_list[i]
    if compare * 2 < size_list[i]:
        break
    cnt += 1

print(cnt)

Solution (Python):
input()
A = list(map(int, input().split())); A.sort()

s = 0
l = 0
for i in range(len(A)):
    if s * 2 < A[i]:
        l = i
    s += A[i]
print(len(A) - l)

Solution (Python):
import numpy as np

N = int(raw_input())
A = map(lambda x:int(x), raw_input().split())

A.sort()

A = np.asarray(A)
S = np.zeros_like(A)
s=0
for i in range(N):
    s += A[i]
    S[i] = s



index = np.where(A[1:] - S[:-1]*2 > 0)[0]
if index.shape[0]:
    print N - index[-1]-1
else:
    print N

Solution (Python):
n = input()
A = map(int, raw_input().split())
A.sort()
s = 0
ans = 1
for a in A:
    if a <= 2*s:
        ans += 1
    else:
        ans = 1
    s += a
print ans

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    a = LI()
    a.sort()
    r = 1
    t = a[0]
    for ai in a[1:]:
        if t*2 < ai:
            r = 1
        else:
            r += 1
        t += ai

    return r

print(main())

Solution (Python):



def identity(x):
    return x

def mapv(f,s):
    return list(map(f,s))

def readln():
    _res = mapv(int,str(input()).split(' '))
    return _res

def seq(n,f=(lambda x: 0)):
    return [f(i) for i in range(0,n)]

n = int(input())
a = sorted(readln())
s = seq(n)
v = 0
s[0] = a[0]
for i in range(1,n):
    s[i] = s[i-1] + a[i]
for i in range(1,n):
    index = n - 1 - i
    if s[index] << 1 >= a[index + 1]:
        v = i + 1
    else: break
print(v)

Solution (Python):
n = input()
a = map(int,raw_input().split(' '))
a.sort(reverse=True)
s = 0
t = n
for i in xrange(len(a)-1,1,-1) :
    s += a[i]
    if s * 2 < a[i-1] : t = i
print t

Solution (Python):

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

l = 0
size = 0

for i in range(N - 1):
    size += A[i]

    if A[i + 1] > 2 * size:
        l = i + 1

ans = N - l

print(ans)

Solution (Python):

def paku(N, A, mid):
    if mid == 0:
        return False

    size = sum(A[:mid])

    for i in range(mid, N):
        if A[i] <= 2*size:
            size += A[i]
        else:
            return False

    return True


N = int(input())
A = [int(i) for i in input().split()]
A.sort()

top = N
btm = 0

while top - btm > 1:
    mid = (top + btm) // 2

    if paku(N, A, mid):
        top = mid
    else:
        btm = mid

ans = N - top + 1

print(ans)

Solution (Python):


num = int(input())
l_cre = list(map(int, input().split()))
l_cre.sort()

counter = 0
now_size = 0

for i in range(len(l_cre) - 1):
    now_size += l_cre[i]
    if now_size * 2 >= l_cre[i + 1]:
        counter += 1
    else:
        counter = 0

counter += 1

print(counter)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    i = 1
    j = N - 1
    x = sum(A)
    while j > 0:
        if (x - A[j]) * 2 >= A[j]:
            i += 1
        else:
            break
        x -= A[j]
        j -= 1
    print(str(i))

main()

Solution (Python):
m = int(input())
n = list(map(int,input().split()))

n.sort()
SUM = 0
count = 0
for i in range(len(n)-1):
    SUM += n[i]
    if n[i+1] > SUM*2:
        count = i+1
print(len(n)-count)

Solution (Python):

N=input()
A=map(int, raw_input().split())
A.sort()


cur = 0
brk=0
for i in xrange(len(A)):
    v=A[i]
    if i !=0 and v > cur*2:

        brk=i
    cur+=v

print len(A) - brk

Solution (Python):

import sys
from itertools import accumulate


def main():
    
    N = int(input())
    As = sorted([int(x) for x in input().split()])
    print(As, file=sys.stderr)

    
    Bs = list(accumulate(As))
    print(Bs, file=sys.stderr)

    M = 0
    Rs = [A / B for A, B in zip(As[1:N], Bs[0:N-1])]
    for i, R in enumerate(Rs):
        if R > 2:
            M = i + 1

    
    print(N - M, file=sys.stderr)
    print(N - M)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())
A.sort()

sum = A[0]
ans = 1
for a in A[1:]:
	if sum*2 < a:
		ans = 1
	else:
		ans += 1
	sum += a
print ans

Solution (Python):
def gattai(ar,i):
    sm = sum(ar[:i+1])
    idx = i
    while True:
        if idx == len(ar)-1:
            return len(ar)
        elif ar[idx+1] <= sm*2:
            sm += ar[idx+1]
            idx += 1
            continue
        else: return i-idx-1

n = int(input())
ar = list(map(int, input().split()))
ar.sort()

ans = 0
idx = 0
while ans <= 0:
    hoge = gattai(ar, idx)
    ans += hoge
    idx = abs(ans)

print(ans)

Solution (Python):
def search_sorted(x, xs):
    '''
    >>> search_sorted(3, range(10))
    3
    >>> search_sorted(3, [0, 1, 3, 3, 3, 5])
    4
    >>> search_sorted(3, [0, 1, 3, 3])
    3
    >>> search_sorted(1, [1, 1])
    1
    '''
    i = 0
    j = len(xs)
    while j - i > 1:
        m = (i + j) // 2
        if xs[m] <= x:
            i = m
        elif x < xs[m]:
            j = m
    return i

class FenwickTree:
    '''
    >>> tree = FenwickTree(5)
    >>> tree.add(0, 3)
    >>> tree.add(4, 2)
    >>> tree.add(2, 7)
    >>> tree.sum(5)
    12
    >>> tree.sum(3)
    10
    >>> tree.sum(2)
    3
    >>> tree.sum(1)
    3
    >>> tree.sum(0)
    0

    '''
    def __init__(self, n):
        self.array = [0] * n

    def add(self, i, x):
        while i < len(self.array):
            self.array[i] += x
            w = (i + 1) & -(i + 1)
            i += w

    def sum(self, i):
        i -= 1
        s = 0
        while i >= 0:
            s += self.array[i]
            w = (i + 1) & -(i + 1)
            i -= w
        return s


def solve():
    input()
    A = list(map(int, input().split())); A.sort()
    tree = FenwickTree(len(A))
    for i, a in enumerate(A):
        tree.add(i, a)

    answer = 0
    for i in range(len(A)):
        a = A[i]
        j = i
        while True:
            j = search_sorted(a * 2, A)
            a_ = tree.sum(j + 1)
            if a == a_:
                break
            else:
                a = a_
        if j + 1 == len(A):
            answer += 1
    print(answer)

solve()

Solution (Python):

N = int(input())

C = list(map(int, input().split()))

C.sort(reverse=True)

color = 0
size  = -1
comp  = 0
c_color = 0
c_update = True
for i in range(0, N):
    
    if C[i] >= size / 2:
        color += 1
        size = C[i]
        continue
    
    else:
        comp += C[i]
        if c_color == 0 or (c_update and C[i -1] <= C[i] * 2):
            c_color += 1
        else:
            c_update = False
    
    if comp >= size/2:
        color += c_color
        size = comp
        comp = 0
        c_color = 0
        c_update = True
print(color)

Solution (Python):
N = int(input())
a = list(map(int,input().split()))

a.sort()

left = 0
right = N

center = (left+right)//2

def check(i):
	s = sum(a[:i+1])
	now = s
	
	for j in range(i, N-1):
		
		if now*2 < a[j+1]:
			return(False)
		now += a[j+1]
	
	return(True)

while right - left > 1:
	center = (left+right)//2
	
	if check(center):
		right = center
		
	else:
		left = center
		

if check(left):
	print(N-left)
else:
	print(N-right)

Solution (Python):


input()
A = list(reversed(sorted([int(x) for x in input().split()])))
total = sum(A)
for i, a in enumerate(A):
    total -= a
    if total * 2 < a:
        break
print(i + 1)

Solution (Python):
import math
def main():
    global N, A
    N = int(input())
    sizes = list(map(int, input().split()))
    A = list(zip(list(range(1, N+1)), sizes))  
    A.sort(key=lambda x:x[1])
    print(N - binary_search_for_integer(N-1, -1))

def binary_search_for_integer(ok, ng):
    while math.fabs(ok-ng) > 1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def solve(x):  
    if x != 0:
        size = sum([a[1] for a in A[:x]]) + A[x][1]
    else:
        size = A[x][1]

    for i in range(1, N-x):
        if A[x+i][1] <= 2*size:
            size += A[x+i][1] 
        else:
            return False

    return True


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left

n=int(raw_input())
a=map(int,raw_input().split())
sa=sorted(a)
s=[0]*n
s[0]=sa[0]
for i in xrange(n-1):
    s[i+1]+=s[i]+sa[i+1]
idx=bisect_left(sa,(sa[n-1]+1)/2)
ans=n-idx
f=0
for i in xrange(idx-1,-1,-1):
    if f==0 and s[i]*2>=sa[i+1]:
        f=1
        ans+=1
    else:
        if f==1 and s[i]*2>=sa[i+1]:
            ans+=1
        else:
            break
print ans

Solution (Python):
N = int(raw_input())
A = list(sorted(map(int, raw_input().split())))

a = A[0]
n = 0
for i in xrange(1, N):
    if 2*a < A[i]:
        n = i
    a += A[i]
print N - n

Solution (Python):
n = input()
a = map(int, raw_input().split())
a = sorted(a)

cumsums = []
cum = 0
for i in xrange(n):
    cum += a[i]
    cumsums.append(cum)
i = n - 1
survivors = 1
while i > 0:
    if a[i] <= cumsums[i-1] * 2:
        survivors += 1
        i -= 1
        continue
    break
print survivors

Solution (Python):
import sys

INF = 10**9+7

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def nal(): return list(map(int, stdin.readline().split()))
def ns(): return stdin.readline().strip()
def nsl(): return list(stdin.readline().strip())
def ni(): return int(stdin.readline())


n = ni()
a = nal()

m = max(a)
a.sort()

c = 0
tmp = 0
for i in range(n-1):
    tmp = a[i] + tmp
    if(tmp*2 < a[i+1]):
        c = i+1


print(n - c)

Solution (Python):

def getLnInputs():
    return input().split()


def getLnIntInputs():
    return list(map(int, getLnInputs()))


def main():
    N = getLnIntInputs()[0]
    A = sorted(getLnIntInputs())

    eatables = []
    eatables_sum = 0

    for c in range(N):
        if len(eatables) <= c:
            eatables.append(A[c])
            eatables_sum += A[c]

        for idx in range(len(eatables), N):
            s = A[idx]
            if s > 2 * eatables_sum:
                break
            eatables.append(s)
            eatables_sum += s

        if len(eatables) == N:
            print(N - c)
            break

    return


main()

Solution (Python):
N = int(raw_input())
A = sorted(map(int, raw_input().split()))

def check(i):
    x = A[i]
    for j, a in enumerate(A):
        if j == i:
            continue
        if a > x * 2:
            return False
        else:
            x += a
    return True

if check(0) == True:
    print N
    exit()
if check(N-1) == False:
    print 0
    exit()

low = 0
high = N - 1
t = (low + high) / 2
while high - low > 1:
    v = check(t)
    if v:
        high = t
    else:
        low = t
    t = (low + high) / 2
print N - t - 1

Solution (Python):
N = int(input())
AA = sorted(map(int, input().rstrip().split()))
cur_size = AA[0]
colorSum = 1
for A in AA[1:]:
    if cur_size * 2 >= A:
        colorSum += 1
    else:
        colorSum = 1
    cur_size += A
print(colorSum)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()

a_sum = [0 for i in range(n)]
a_sum[0] = a[0]
for i in range(1, n):
    a_sum[i] = a_sum[i - 1] + a[i]

cnt = 1
for i in range((n - 1) - 1, -1, -1):
    if a[i + 1] <= a_sum[i] * 2:
        cnt += 1
    else:
        break

print(cnt)

Solution (Python):
n = int(input().strip())
a = [int(x) for x in input().strip().split()]

a.sort()
a.reverse()
s = sum(a)

i = 1
for x in a:
  if x > (s - x)*2:
    break
  else:
    s -= x
    i += 1

print(i)

Solution (Python):
n = int(input())
As = list(map(int, input().split()))

As = sorted(As,reverse=True)

def d(*arg):
    
    pass

last = 0
ret = 0
leng = len(As)
for idx,a in enumerate(As):
    if 2*a < last:
        if 2*sum(As[idx:])>=last:
            ret += 1
            d('\t',last,ret,leng,idx,a)
        else:
            d('\t',last,ret,leng,idx,a)
            break
            
    else:
        d('\t',last,ret,leng,idx,a)
        ret += 1
    d('\t\t',last,ret,leng,idx,a)
    last = a
print(ret)

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9


def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()
A = ln()

A.sort()

cum = [A[0]]
for a in A[1:]:
    cum.append(cum[-1] + a)






x2 = len(A) - 1
result = 1
for i in xrange(len(A) - 2, -1, -1):
    
    
    
    if cum[i] * 2 < A[i + 1]:
       break
    
    result += 1

print result

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

A.sort()

answer = 0
size_sum = 0

for i in range(N):
    if size_sum * 2 < A[i]:
        answer = 0
    
    size_sum += A[i]
    answer += 1

print(answer)

Solution (Python):
import sys
from itertools import accumulate

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    Ac = list(accumulate(A))

    ans = 1
    

    for i in range(N - 2, -1, -1):
        if Ac[i] * 2 >= A[i + 1]:
            ans += 1
        else:
            print(ans)
            return

    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
a = sorted(map(int, input().split()))
s = 0
cur = 0
for i, v in enumerate(a):
  if v > 2*s: cur = i
  s += v
print(n-cur)

Solution (Python):
length = int(input())
target = []
target = [int(n) for n in input().split(" ")]
target.sort()
answer = length
temp_len = 0
for i,t in enumerate(target):
    if i == 0:
        before = t
    elif before * 2 < t:
        before += t
        answer -= temp_len
        temp_len = 0
    else:
        before += t
    temp_len += 1
print(answer)

Solution (Python):
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    a.sort()
    s = a[0]
    u = 0
    for i, x in enumerate(a[1:], 1):
        if x > s * 2:
            u = i
        s += x
    print n - u
main()

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
accumuration = [A[0]]
for i in range(1,N):
	accumuration.append(accumuration[i-1]+A[i])
for i in range(N):
	if accumuration[N-i-2]*2 < A[N-1-i]:
		print(i+1)
		exit()
print(N)

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
As.sort()

s = 0
ans = 0
for i in range(len(As)-1):
	s += As[i]
	if s * 2 >= As[i+1]:
		ans += 1
	else:
		ans = 0
ans += 1
print(ans)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
ans=0
sum=0
A.sort()
for i in range(N-1):
	sum+=A[i]
	if A[i+1]>2*sum:
		ans=i+1
print(N-ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()

A = [(a, 1) for a in A]
for i in range(N - 1):
    if A[i][0] * 2 >= A[i + 1][0]:
        A[i + 1] = (A[i][0] + A[i+1][0], A[i][1] + 1)
    else:
        A[i + 1] = (A[i][0] + A[i+1][0], 1)
print(A[N - 1][1])

Solution (Python):
n = int(raw_input())
a = [int(x) for x in raw_input().split()]

a.sort()

s = a[0]
m = 0
for i in xrange(1, n):
	if s * 2 < a[i]:
		m = i
	s += a[i]

print(n - m)