该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

银币（coin）

题目描述

Y 同学面前有 $n$ 堆银币，第 $i$ 堆有 $a_i$ 枚银币。

Y 同学可以选择若干整堆银币带走。设他带走的银币总数为 $S$，剩下的银币总数为 $T$。他希望满足 $S>T$。

请你求出为了满足这个条件，Y 同学至少需要带走多少堆银币。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示至少需要带走的银币堆数。

样例

样例输入 #1

5
2 3 4 1 2

样例输出 #1

2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 2\times 10^5$，$1 \le a_i \le 10^9$。

• 特殊性质 A：保证所有 $a_i$ 相等。
• 特殊性质 B：保证 $a_i \le 2$。