Twins

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ coins with values $a_i$. Choose the minimum number of coins such that their total value is strictly greater than the total value of all remaining coins.

Input

The first line contains $n$. The second line contains $n$ integers $a_i$.

Output

Print the minimum number of coins to take.

Subtasks

General constraints:

• $1 \le n \le 100$.

• $1 \le a_i \le 100$.

• Subtask 1 (20 points): $n \le 10$

• Subtask 2 (30 points): $n \le 50$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

3
2 1 2

Output

2

Explanation

Taking the two coins of value $2$ gives total $4$, strictly larger than the remaining total $1$. One coin is insufficient.