P9787 [ROIR 2020] 最大乘积 (Day2)

**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T1.** ***[Максимальное произведение](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者ShineEternal 给定一个自然数组成的数组 $[a_1,a_2,\ldots,a_n]$。 定义一个数组的权值为这个数组中所有数的和。 请把这个数组划分为两个非空数组 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$，使得它们的权值之积尽量大。 你需要确定能够使得两个数组权值之积最大的 $i$。

第一行，一个整数 $n$，表示元素的个数。 第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组中的元素。

输出能使得 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$ 权值之积最大的 $i$。 若有多解，随意输出一解即可。

#### 【样例 1 解释】 如果你选择 $i=1$，则权值之积为 $1 \cdot (2+3) = 5$。 如果你选择 $i=2$，则权值之积为 $(1+2) \cdot 3 = 9$。 #### 【数据范围】 对于 $100\%$ 的数据，$2 \le n \le 2\cdot 10^5, 1 \le a_i \le 10^9$。 具体数据限制如下表： |子任务编号|分值|限制|附加限制| |:-:|:-:|:-:|:-:| |$1$|$10$|$2 \le n \le 5000$|$\sum a_i \le 10^9$| |$2$|$10$|$2 \le n \le 5000$|$a_1 = a_2 = \ldots = a_n$| |$3$|$20$|$2 \le n \le 5000$|$a_i \le 10^9$| |$4$|$20$|$2 \le n \le 200000$|$\sum a_i \le 10^9$| |$5$|$20$|$2 \le n \le 200000$|$a_1 = a_2 = \ldots = a_n$| |$6$|$20$|$2 \le n \le 200000$|$a_i \le 10^9$|