Imagine you have a twin sibling. Imagine a typical morning before school in your family. Your parents have already left (to go do whatever adults do during the day) and have rudely forgotten to leave any food for lunch. They have, however, left some coins to buy lunch with. To be specific, \(n\) coins of arbitrary value \(a_1, a_2, ... ,a_n\). Your parents have not split the coins, however.

Since you have woken up before your (clearly inferior) twin you have decided to split the lunch money. You decide to split the money unequally to buy yourself suitably superior lunch; so you want to select a subset of coins such that the sum is strictly larger than the sum of the remaining coins. As the superior and cunning twin you correctly realise you cannot take too much extra money else your twin will get suspicious. So you want to take the minimum number of coins whose sum of values is strictly larger than the sum of the remaining coins.

Determine what minimum number of coins you need to take to divide the money in the described way.

Input Specification

Two lines. The first contains an integer \(n\), \((1 \leq n \leq 100)\).

The second line contains \(n\) space-separated integers \(a_1, a_2, a_3,...,a_n\) \((1 \leq a_i \leq 100)\) - the value of each coin.

Output Specification

Print the minimum number of coins needed to divide the money as described.

Sample Input 1

2
3 3

Sample Output 1

2

Sample Input 2

5
3 5 4 5 1

Sample Output 2

2