活动奖励盒里有 $n$ 枚代币，第 $i$ 枚面值为 $a_i$。小泽需要拿走一些代币，使自己拿到的总面值严格大于盒中剩余代币的总面值。

为了尽量少拿代币，他会在满足严格大于条件的所有方案中选择枚数最少的一种，计数器显示这个最少枚数。

输入格式

第一行输入 $n$；第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出使拿走总面值严格大于剩余总面值所需的最少代币数。

2
3 3

2

3
2 1 2

2

9
38 43 38 67 81 51 74 61 56

4

样例解释

两枚代币都是 3。只拿一枚时两边同为 3，不满足严格大于，因此必须拿两枚。

数据范围与约定

• $1\le n\le100$
• $1\le a_i\le100$