当前没有测试数据。

硬币分配

题目描述

Y 同学是一个精打细算的人。某天早上，他在桌上发现了 $N$ 枚硬币，第 $i$ 枚硬币的面值为 $a_i$。

Y 同学还有一个双胞胎兄弟。为了在不引起兄弟怀疑的情况下尽可能多地拿走硬币，Y 同学制定了以下策略：

1. 他要拿走一部分硬币，使得他拿走的硬币面值总和严格大于剩下的硬币面值总和（即兄弟能得到的硬币总和）。
2. 在满足上述条件的前提下，他希望拿走的硬币数量尽可能少。

请你帮助 Y 同学计算，他最少需要拿走多少枚硬币。

输入格式

第一行包含一个整数 $N$，表示硬币的数量。 第二行包含 $N$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_N$，表示每枚硬币的面值。

输出格式

输出一行一个整数，表示 Y 同学最少需要拿走的硬币数量。

样例

样例输入 #1

2
3 3

样例输出 #1

2

样例输入 #2

3
2 1 2

样例输出 #2

2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 100$，$1 \le a_i \le 100$。