Problem Description

Translated from ROIR 2020 Day2 T1. Максимальное произведение, 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.

Input Format

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 Format

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.

3
1 2 3

2

Hint

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:

Translated by ChatGPT 5