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. 
class Node:

    def __init__(self, key, parent=None):
        self.count = 1
        self.key = key
        self.parent = parent
        self.left, self.right = None, None

    def hasLeft(self):
        return self.left is not None

    def hasRight(self):
        return self.right is not None

    def height(self):
        if self.hasLeft():
            leftH = self.left.height()
        else:
            leftH = 0
        if self.hasRight():
            rightH = self.right.height()
        else:
            rightH = 0
        if leftH == 0 and rightH == 0:
            return 0
        else:
            return 1 + max(leftH, rightH)

    def balance(self):
        if self.hasLeft():
            leftH = self.left.height()
        else:
            leftH = 0
        if self.hasRight():
            rightH = self.right.height()
        else:
            rightH = 0
        return leftH - rightH

    def inOrderWalk(self):
        if self.hasLeft():
            for k in self.left.inOrderWalk():
                yield k
        for _ in range(self.count):
            yield self.key
        if self.hasRight():
            for k in self.right.inOrderWalk():
                yield k

    def preOrderWalk(self):
        for _ in range(self.count):
            yield self.key
        if self.hasLeft():
            for k in self.left.preOrderWalk():
                yield k
        if self.hasRight():
            for k in self.right.preOrderWalk():
                yield k

    def postOrderWalk(self):
        if self.hasLeft():
            for k in self.left.postOrderWalk():
                yield k
        if self.hasRight():
            for k in self.right.postOrderWalk():
                yield k
        for _ in range(self.count):
            yield self.key

class AVLTree:

    def __init__(self):
        self.root = None
        self.count = 0

    def __len__(self):
        return self.count

    def search(self, key):
        target = self.root
        while target is not None:
            if key == target.key:
                return True
            elif key < target.key:
                target = target.left
            else:
                # key > target.key
                target = target.right
        return False

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            current = self.root
            while current is not None:
                if key == current.key:
                    current.count += 1
                    return
                elif key < current.key:
                    target = current
                    current = current.left
                else:
                    # key > current.key
                    target = current
                    current = current.right
            if key > target.key:
                target.right = Node(key, target)
                self.rebalance(target.right)
            else:
                target.left = Node(key, target)
                self.rebalance(target.left)
        self.count += 1

    def delete(self, key):
        if self.root is None:
            raise KeyError()
        else:
            found = False
            parent, target = None, self.root
            while target is not None:
                if key == target.key:
                    found = True
                    break
                elif key < target.key:
                    parent = target
                    target = target.left
                else:
                    # key > target.key
                    parent = target
                    target = target.right
            if found:
                if target.hasRight():
                    current = target.right
                    while current is not None:
                        replacement = current
                        current = current.left
                    target.key = replacement.key
                    if replacement.hasRight():
                        replacement.parent.left = replacement.right
                        replacement.right.parent = replacement.parent
                    else:
                        replacement.parent.left = None
                elif target.hasLeft():
                    current = target.left
                    while current is not None:
                        replacement = current
                        current = current.right
                    target.key = replacement.key
                    if replacement.hasLeft():
                        replacement.parent.right = replacement.left
                        replacement.left.parent = replacement.parent
                    else:
                        replacement.parent.right = None
                else:
                    # no left or right subtrees
                    if target.key > parent.key:
                        # target is the right subtree of parent
                        parent.right = None
                    else:
                        # target is left subtree of parent
                        parent.left = None
                self.rebalance(parent)
                self.count -= 1
            else:
                raise KeyError()

    def rebalance(self, node):
        bal = node.balance()
        if bal > 1:
            bal = node.left.balance()
            if bal > 1:
                self.rotate_r(node)
            elif bal < -1:
                self.rotate_lr(node)
        elif bal < -1:
            bal = node.right.balance()
            if bal > 1:
                self.rotate_rl(node)
            elif bal < -1:
                self.rotate_l(node)

    def rotate_l(self, r):
        c = r.right
        t1 = r.left
        t2 = c.left
        t3 = c.right
        c.key, r.key = r.key, c.key
        c.left, c.right, r.right, r.left = t1, t2, t3, c
        t1.parent, t2.parent, t3.parent, c.parent = c, c, r, r
    
    def rotate_r(self, r):
        c = r.left
        t1 = c.left
        t2 = c.right
        t3 = r.right
        r.key, c.key = c.key, r.key
        r.left, r.right, c.left, c.right = c, t3, t1, t2
        c.parent, t3.parent, t1.parent, t2.parent = r, r, c, c

    def rotate_lr(self, r):
        c, g = r.left. r.left.right
        t1, t2, t3, t4 = c.left, g.left, g.right, r.right
        r.key, g.key = g.key, r.key
        r.left, r.right = c, g
        g.left, g.right = t3, t4
        t3.parent, t4.parent = g, g
        c.left, c.right = t1, t2
        t1.parent, t2.parent = c, c


    def rotate_rl(self, r):
        c, g = r.right, r.right.left
        t1, t2, t3, t4 = r.left, g.left, g.right, c.right
        r.key, g.key = g.key, r.key
        r.left, r.right = g, c
        g.parent, c.parent = r, r
        g.left, g.right = t1, t2
        t1.parent, t2.parent = g, g
        c.left, c.right = t3, t4
        t3.parent, t4.parent = c, c





if __name__ == "__main__":
    N = int(raw_input())
    coins = [ int(value) for value in raw_input().split()]
    threshold = sum(coins) >> 1
    avl = AVLTree()
    for coin in coins:
        avl.insert(coin)
    stack = [ coin for coin in  avl.root.inOrderWalk() ]
    n, value, lastcoin = 0, 0, 0
    while value <= threshold:
        value += stack.pop()
        n += 1
    print n


