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

两端取币（twins2）

题目描述

$Y$ 同学有 $n$ 枚硬币，它们从左到右排成一行，第 $i$ 枚硬币的面值为 $a_i$。

现在，$Y$ 同学想从这些硬币中取出尽可能少的若干枚，使得被取出的硬币面值总和严格大于剩余所有硬币的面值总和。

但取硬币的方式受到限制：每次操作中，$Y$ 同学只能取走当前最左端或当前最右端的一枚硬币。

你需要求出，在最优选择下，最少需要取走多少枚硬币，才能满足要求。

输入格式

第一行包含一个整数 $n$，表示硬币的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每枚硬币的面值。

输出格式

输出一个整数，表示最少需要取走的硬币数量。

样例

样例输入 #1

4
4 1 2 10

样例输出 #1

1

样例输入 #2

4
1 100 100 1

样例输出 #2

3

数据范围与约定

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

特殊性质 $A$：保证序列单调不降，即对所有 $1 \le i < n$，均有 $a_i \le a_{i+1}$。

特殊性质 $B$：保证序列单调不增，即对所有 $1 \le i < n$，均有 $a_i \ge a_{i+1}$。

特殊性质 $C$：保证所有硬币面值均相同。