P9787 [ROIR 2020] Maximum Product (Day2)

**Translated from [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)***, translator: ShineEternal. You are given an array of natural numbers $[a_1,a_2,\ldots,a_n]$. Define the weight of an array as the sum of all numbers in the array. Please split this array into two non-empty arrays $[a_1,a_2,\ldots,a_i]$ and $[a_{i+1},a_{i+2},\ldots,a_n]$, so that the product of their weights is as large as possible. You need to determine the $i$ that maximizes the product of the weights of the two arrays.

The first line contains an integer $n$, representing the number of elements. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the elements in the array.

Output an $i$ that maximizes the product of the weights of $[a_1,a_2,\ldots,a_i]$ and $[a_{i+1},a_{i+2},\ldots,a_n]$. If there are multiple answers, you may output any one of them.

#### Sample 1 Explanation If you choose $i=1$, then the product of weights is $1 \cdot (2+3) = 5$. If you choose $i=2$, then the product of weights is $(1+2) \cdot 3 = 9$. #### Constraints For $100\%$ of the testdata, $2 \le n \le 2\cdot 10^5, 1 \le a_i \le 10^9$. The detailed limits are shown in the table below: |Subtask ID|Score|Limit|Additional Limit| |:-:|:-:|:-:|:-:| |$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$| Translated by ChatGPT 5