Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like.

Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, n coins of arbitrary values a1, a2, ..., an. But as Mom was running out of time, she didn't split the coins for you two. So she scribbled a note asking you to split the money equally.

As you woke up, you found Mom's coins and read her note. "But why split the money equally?" — you thought. After all, your twin is sleeping and he won't know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is strictly larger than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you've decided to stick to the following strategy to avoid suspicions: you take the minimum number of coins, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what minimum number of coins you need to take to divide them in the described manner.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of coins. The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the coins' values. All numbers are separated with spaces.

Output

In the single line print the single number — the minimum needed number of coins.

Examples

Input

2
3 3


Output

2


Input

3
2 1 2


Output

2

Note

In the first sample you will have to take 2 coins (you and your twin have sums equal to 6, 0 correspondingly). If you take 1 coin, you get sums 3, 3. If you take 0 coins, you get sums 0, 6. Those variants do not satisfy you as your sum should be strictly more that your twins' sum.

In the second sample one coin isn't enough for us, too. You can pick coins with values 1, 2 or 2, 2. In any case, the minimum number of coins equals 2. 
#!/usr/bin/python3

"""
// math.hypot(x1-x2, y1-y2)
sqrt( (x1-x2)**2 + (y1-y2)**2 )

Fold All Levels ( ALT + 0 )
Unfold All Levels ( ALT + SHIFT + 0 )

list.index(element)

problème de la corde
def p():
    N = int(input())
    tab = map(int, list(input().split()))
    d = {i+1: val for i, val in enumerate(tab)}
    for i in range(2, N+1):
        for j in range(1, i):
            d[i] = max(d[i], d[j] + d[i-j])
    print(d[N])


#Complexity: O(max(log2(a), log2(b)))
def gcd(a,b):
	while b:
		a,b=b,a%b
	return a

#Complexity: O(max(log2(a), log2(b)))
def lcm(a,b):
	w=a//gcd(a,b)
	return w*b

"""


import sys
import math
import itertools
from sys import stdin, stdout
from functools import lru_cache

import statistics
import datetime
import collections


M_PI = 3.14159265358979323846


sys.setrecursionlimit(5000) # default: 1000
CACHE_MAX_SIZE = 5000

## ---------------------------------------------------------------------------

def problemA():
    n = intput()
    for i in range(n):
        m = intput()
        coins = intlist()
        S = sum(coins)
        pos = get_all_subsums(coins, S//2)
        i = S//2
        while i != 0:
            if i in pos:
                break
            i -= 1
        print(S-2*i)




def get_all_subsums(elems:[int], target=-1, maxi=-1) -> {int}:
    """UVA: 562"""
    if target!=-1 and maxi==-1: maxi=target
    elif maxi==-1: maxi=sum(elems)  # sum//2 ?
    pos = set()
    for e in elems:
        if e > maxi: continue
        if target in pos: break
        tmp = pos.copy()
        pos.add(e)
        for a in tmp:
            if a+e <= maxi: pos.add(a+e)
            if a+e == target: break
    return pos


def problemB():
    n = intput()
    arr = intlist()
    arr.sort(reverse=True)
    S = sum(arr)
    P = 0
    for i in range(n):
        P += arr[i]
        S -= arr[i]
        if P > S:
            break
    print(i+1)




def main():
    problemB()


## ---------------------------------------------------------------------------

def intput():
    return int(stdin.readline())
def floatput():
    return float(stdin.readline())
def intlist():
    return list(map(int, stdin.readline().split()))
def floatlist():
    return list(map(float, stdin.readline().split()))

## ---------------------------------------------------------------------------

class Point:
    def __init__(self, x=0, y=0, z=0):
        self.x, self.y, self.z = x, y, z
    def __add__(self, point):
        return Point(self.x+point.x, self.y+point.y, self.z+point.z)
    def __sub__(self, point):
        return Point(self.x+point.x, self.y+point.y, self.z+point.z)
    def __mul__(self, alpha: float):
        return Point(self.x*alpha, self.y*alpha, self.z*alpha)
    def __truediv__(self, alpha: float):
        return Point(self.x/alpha, self.y/alpha, self.z/alpha)
    def __eq__(self, point):
        return self.x == point.x and self.y == point.y and self.z == point.z
    def __ne__(self, point):
        return not self.__eq__(point)
    @staticmethod
    def distance(p1, p2):
        return math.sqrt((p1.x-p2.x)**2 + (p1.y-p2.y)**2 + (p1.z-p2.z)**2)
    @staticmethod
    def manhattan_distance(p1, p2):
        return abs(p1.x-p2.x) + abs(p1.y-p2.y) + abs(p1.z-p2.z)

## ---------------------------------------------------------------------------

def isBissextile(year: int) -> bool:
    return not(year%400) or ((year%100) and not(year%4))

def getCombinations(my_list):
    combinations = []
    for L in range(0, len(my_list)+1):
        for subset in itertools.combinations(my_list, L):
            combinations.append(subset)
    return combinations

def is_palindromic(value:str) -> bool:
    return str(value) == str(value)[::-1]

def factorial(n:int) -> int:
    f = 1
    for i in range(2, n+1):
        f *= i
    return f

def numberToBase(n:int, base:int) -> [int]:
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % base))
        n //= base
    return digits[::-1]

def toRoman(nb:int) -> str:
    tab = ['I', 'V', 'X', 'L', 'C', 'D', 'M']
    power = 0
    answer = ""
    while nb!=0:
        num = nb%10
        nb//=10
        if   num==0: pass
        elif num==1: answer = tab[power] + answer
        elif num==2: answer = tab[power] + tab[power] + answer
        elif num==3: answer = tab[power] + tab[power] + tab[power] + answer
        elif num==4: answer = tab[power] + tab[power+1] + answer
        elif num==5: answer = tab[power+1] + answer
        elif num==6: answer = tab[power+1] + tab[power] + answer
        elif num==7: answer = tab[power+1] + tab[power] + tab[power] + answer
        elif num==8: answer = tab[power+1] + tab[power] + tab[power] + tab[power] + answer
        elif num==9: answer = tab[power] + tab[power+2] + answer
        power+=2
    return answer


## ---------------------------------------------------------------------------

def corde():
    N = int(input())
    tab = map(int, list(input().split()))
    d = {i+1: val for i, val in enumerate(tab)}
    for i in range(2, N+1):
        for j in range(1, i):
            d[i] = max(d[i], d[j] + d[i-j])
    print(d[N])


def LIS(X):
    M = [-1]*(len(X)+1) # M[j] contient l'index k du plus petit élément X[k] de la suite de taille j finissant par X[k] 
    P = [-1]*(len(X))   # P[k] contient le prédécesseur de X[k]
    L=0
    for i in range(len(X)): # Binary search for largest positive j<=L # X[M[j]] < X[i]
        deb=1
        fin=L
        while deb <= fin:
            mid = math.ceil((1.0*deb+fin)/2)
            if X[M[mid]] < X[i]:
                deb = mid+1
            else:
                fin = mid-1
        newL = deb        
        P[i] = M[newL-1]
        M[newL] = i
        if newL > L:
            L = newL
    S = [-1]*L
    index = M[L]
    for i in reversed(range(0, L)):
        S[i]  = X[index]
        index = P[index]
    #print(S)
    return L

def knapsack0(capacity, items):
    """Multiple occurences for each item."""
    dp = [False]*(capacity+1)
    dp[0] = True
    for i in range(1,capacity+1):
        j=0
        while j<len(items) and not(dp[i]):
            if i-items[j]>=0 and dp[i-items[j]]:
                dp[i]=True
            j+=1
    answer = capacity
    while not(dp[answer]):
        answer -= 1
    return answer


def knapsack3(W , wt , val , n=-1, init=True):
    """2D knapsack with values."""
    if init: # init the memoization
        maxValue = 10000
        maxPieces = len(wt)+1
        knapsack3.dp = [ [-1 for _i in range(maxPieces)] for _j in range(maxValue) ]
    if n==-1: # init the number of pieces
        n=len(wt)
    if knapsack3.dp[W][n] != -1: # if set of params already computed
        return knapsack3.dp[W][n]
    
    if n == 0 or W == 0: # Base Case : no capacity OR no item
        return 0
    if wt[n-1] > W: # nth item is bigger than knapsack's capacity
        return knapsack3(W , wt , val , n-1, False)
    else: # two cases : nth item included or excluded
        return max(val[n-1] + knapsack3(W-wt[n-1] , wt , val , n-1, False), 
                knapsack3(W , wt , val , n-1, False)) 



def minCoinChange(value, pieces, n=-1, init=True):
    """value : the sum to be returned - n : the number of pieces we can use"""
    if init: # init the memoization
        maxValue = 10000
        maxPieces = len(pieces)
        minCoinChange.dp = [ [-1 for i in range(maxPieces)] for j in range(maxValue) ]
    if n==-1: # init the number of pieces
        n=len(pieces)-1
    if minCoinChange.dp[value][n] != -1: # if set of params already computed
        return minCoinChange.dp[value][n]
    
    if n==0 or value==0:
        if value%pieces[0]!=0:
            return inf
        else:
            return value//pieces[0]
    elif value<0:
        return inf
    else:
        minCoinChange.dp[value][n] = min( minCoinChange(value-pieces[n], pieces, n, False)+1, minCoinChange(value, pieces, n-1, False) )
        return minCoinChange.dp[value][n]


def coinChange(value, pieces, n=-1, init=True):
    """value : the sum to be returned - n : the number of pieces we can use #OK"""
    if init: # init the memoization
        maxValue = 10000
        maxPieces = len(pieces)
        coinChange.dp = [ [-1 for i in range(maxPieces)] for j in range(maxValue) ]
    if n==-1: # init the number of pieces
        n=len(pieces)-1
    if coinChange.dp[value][n] != -1: # if set of params already computed
        return coinChange.dp[value][n]

    if n==0 or value==0:
        return 1
    elif value<0:
        return 0
    else:
        coinChange.dp[value][n] = coinChange(value-pieces[n], pieces, n, False) + coinChange(value, pieces, n-1, False)
        return coinChange.dp[value][n]



## ---------------------------------------------------------------------------

# primes
# levenstein
# convex hull

# for line in sys.stdin:
# sys.maxsize


# "{0:b}".format(37)
# returns a str of binary

'''
n, k = map(int, input().split())
days = list(map(int, input().split()))

'''

# from collections import Counter
# c = Counter(uneListe)

# sort map by value
# sorted(d.items(), key=lambda x: x[1])


# liste[0:10:2]
# defaultdic ??

# c.islower()


def binary_encode(i, num_digits):
    return np.array([i >> d & 1 for d in range(num_digits)])


def generate_primes(n:int) -> [int]:
    """Return primes in [0,n]."""
    if n<2: return []

    is_prime = [False, False] + [True]*(n-1)
    primes=[2]
    if n>=3: primes.append(3)

    for i in range(5, n+1, 6):
        if is_prime[i]:
            primes.append(i)
            j = i**2
            while j<=n:
                is_prime[j] = False
                j += (2*i)
        if i+2<=n and is_prime[i+2]==True:
            primes.append(i+2)
            j = (i+2)**2
            while j<=n:
                is_prime[j] = False
                j+=(2*i+4)
    return primes



## ---------------------------------------------------------------------------
def knapSack3(Weight, wt, val):
    @lru_cache(maxsize=CACHE_MAX_SIZE)  # store maxsize calls
    def knapsack(W, n):
        if n == 0 or W == 0 :
            return 0
        if wt[n-1] > W:
            return knapsack(W, n-1)
        else:
            return max(val[n-1] + knapsack(W-wt[n-1], n-1), knapsack(W, n-1))
    return knapsack(Weight, len(wt))

## ---------------------------------------------------------------------------

if __name__ == "__main__":
    main()

