Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие
i и
j (
i<=j), что сумма всех элементов массива от
ai до
aj включительно будет максимальна. Индексация элементов начинается с 1.
Входные данные
В первой строке задается натуральное число
n <= 100000 — количество элементов в массиве. В следующих
n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.
Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то
j должно быть минимально возможным, а при равных
j значение
i должно быть максимально возможным. В первой строке выведите
i, во второй -
j.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
-1
2
3
-2
2 |
2
3 |
| 2 |
7
2
-2
3
-1
5
-2
7 |
3
7 |
Запрещенные операторы: sort; min; max; reverse; count; sum; index