Maximum Product Partition

You are given an array of natural numbers ( [a_1, a_2, \ldots, a_n] ). The weight of an array is defined as the sum of its elements. Partition the array into two non-empty contiguous parts ([a_1, a_2, \ldots, a_i]) and ([a_{i+1}, a_{i+2}, \ldots, a_n]) (with (1 \le i < n)) such that the product of their weights is maximized. In other words, let (S_1 = \sum_{k=1}^{i} a_k) and (S_2 = \sum_{k=i+1}^{n} a_k), you need to find the index (i) for which (S_1 \times S_2) is maximum. If there are multiple indices yielding the maximum product, output the smallest index.

inputFormat

The first line contains an integer (n) ((2 \le n \le 10^5)) denoting the number of elements in the array. The second line contains (n) space-separated natural numbers (a_1, a_2, \ldots, a_n) (each (a_i) is between 1 and (10^9)).

outputFormat

Output a single integer (i) ((1 \le i < n)) representing the partition index such that the product of the weights of the two parts is maximized.

sample

5
1 2 3 4 5

3