两端取币（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$。

测试点编号	分值	$n \le$	$a_i \le$	特殊性质

| :----------: | :--: | :-------------: | :-------: | :--: | | $1 \sim 4$ | $20$ | $20$ | $20$ | 无 | | $5 \sim 8$ | $20$ | $10^3$ | $10^5$ | $A$ | | $9 \sim 12$ | $20$ | $2 \times 10^5$ | $10^9$ | $B$ | | $13 \sim 16$ | $20$ | $2 \times 10^5$ | $10^9$ | $C$ | | $17 \sim 20$ | $20$ | $2 \times 10^5$ | $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$：保证所有硬币面值均相同。