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

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

Формат входных данных

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

Формат выходных данных

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

Ограничения

1 ≤ ai ≤ 109

2 ≤ n ≤ 2 ⋅ 105

Система оценивания

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

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1102 ≤ n ≤ 5000, Сумма всех ai не превосходит 109полная
2102 ≤ n ≤ 5000, Все ai равны1полная
320 2 ≤ n ≤ 5000, ai ≤ 1091, 2полная
4202 ≤ n ≤ 200000, Сумма всех ai не превосходит 1091полная
5202 ≤ n ≤ 200000, Все ai равны2полная
6202 ≤ n ≤ 200000, ai ≤ 1091, 2, 3, 4, 5полная

Замечание

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

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 2 3
2

0.111s 0.011s 13