Maximum Product

Interview

Time limit2sMemory limit512 MB

Summary

Split the array after one index so the product of the two part sums is maximized, and print that index.

Level: Easy3 of 10
Topics: Prefix sum, Array, Greedy, Math
Solved: No attempts yet

Problem

An array of positive integers [a_1, a_2, \ldots, a_n] is given. The weight of an array is the sum of its elements.

Cut the given 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.

Write a program that, for a given array, determines the element after which the array must be cut so that the product of the weights of the resulting arrays is maximal.

Input

The first line of input contains the integer $n$ , the number of elements in the array. ( $2 \le n \le 2 \cdot 10^5$ )

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the elements of the array. ( $1 \le a_i \le 10^9$ )

Output

Print one number: the index of the element after which the given array must be cut. If several optimal answers exist, you may print any of them.

Hint

If the cut is made after the first element, the product of the weights is $1 \cdot (2 + 3) = 5$ , and if after the second, it is $(1 + 2) \cdot 3 = 9$ .

Examples1

Example 1
Input
```
3
1 2 3
```
Expected output
```
2
```