19874번 - Максимальное произведение 서브태스크스페셜 저지다국어

Задан массив натуральных чисел [a₁, a₂, . . . , a_n]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a₁, a₂, . . . , a_i] и [a_i+1, a_i+2, . . . , a_n] так, чтобы произведение их весов было как можно больше.

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

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 · 10⁵). В следующей строке находятся n целых чисел a₁, a₂, . . . , a_n — элементы массива (1 ≤ a_i ≤ 10⁹).

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

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