| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 10 | 2 ≤ n ≤ 5000, Сумма всех ai не превосходит 109 | полная | |
| 2 | 10 | 2 ≤ n ≤ 5000, Все ai равны | 1 | полная |
| 3 | 20 | 2 ≤ n ≤ 5000, ai ≤ 109 | 1, 2 | полная |
| 4 | 20 | 2 ≤ n ≤ 200000, Сумма всех ai не превосходит 109 | 1 | полная |
| 5 | 20 | 2 ≤ n ≤ 200000, Все ai равны | 2 | полная |
| 6 | 20 | 2 ≤ n ≤ 200000, ai ≤ 109 | 1, 2, 3, 4, 5 | полная |
Если сделать разрез после первого элемента, произведение весов равно 1 ⋅ (2 + 3) = 5, а если после второго, то (1 + 2) ⋅ 3 = 9
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 |
|
|