Максимальное произведение

Задан массив натуральных чисел [a1, a2, . . . , an]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a1, a2, . . . , ai] и [ai+1, ai+2, . . . , an] так, чтобы произведение их весов было как можно больше.

Требуется написать программу, которая по заданному массиву определяет, после какого элемента его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 · 105). В следующей строке находятся n целых чисел a1, a2, . . . , an — элементы массива (1 ≤ ai ≤ 109).

Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.

Если сделать разрез после первого элемента, произведение весов равно 1 · (2 + 3) = 5, а если после второго, то (1 + 2) · 3 = 9.