ЗАДАЧА E

Заготовка сена

Имя входного файла:hay.in
Имя выходного файла:hay.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

А Матроскин Гаврюшу обучал. Учил его всему. Палку в воду бросит, а теленок принесет. Скажет ему: «Лежать!» - и Гаврюша лежит. Прикажет ему Матроскин: «Взять! Куси!» – тот сразу бежит и бодаться начинает. Прекрасный сторожевой бык из него получался.


Э.Успенский «Дядя Федор, пес и кот», глава 19



Вместе с тем Гаврюша очень быстро растет, и аппетит у него – будь здоров. Так что кот Матроскин кроме тренировки Гаврюши занимается заготовкой сена для него, ну а теленок Гаврюша это сено ест. Матроскин каждый день записывает сумму прихода и расхода сена. Матроскин хочет иметь возможность быстро находить по своим записям период, за который запасы сена увеличились больше всего. Помогите ему в этом.

У Матроскина есть массив целых чисел, в котором индексом элемента массива является номер дня от начала записей (первый день имеет индекс 0), а значениями элементов – разность между приходом и расходом сена в соответствующий день. Матроскин хочет найти в своих записях такой период из нескольких дней подряд, за который запасы сена увеличились больше всего.

Входные данные


Первая строка входного файла содержит единственное натуральное число N (1 <= N <= 5000) – количество дней в записях Матроскина. Вторая строка содержит N целых чисел, по модулю не превосходящих 106 – значения «приход–расход» в каждый из дней. Числа разделяются пробелами. Хотя бы одно из данных N чисел неотрицательно.

Выходные данные


В первую строку выходного файла выведите три целых числа – максимальную сумму за некоторый период времени, индекс начала периода времени и индекс конца периода. Индексы нумеруются с нуля. Во вторую строку выходного файла через пробел выведите значения «приход-расход» за этот период времени. Если существует несколько периодов времени, за которые запасы сена увеличились больше всего, то выведите более длинный из них. Если и таких периодов несколько, то выведите период с меньшим индексом начала.

Пример


hay.in hay.out
12
-3 4 -2 5 0 -2 7 1 -5 3 1 -2
13 1 7
4 -2 5 0 -2 7 1
12
3 -3 -1 6 -3 1 -5 5 0 -1 4 1
9 7 11
5 0 -1 4 1


[Вложение не найдено]

Данная задача была любезно предоставлена компанией NIX Solutions (http://www.nixsolutions.com/)