EduBrick

L. Отрезок с максимальной суммой

2000 мс · 256 МБ · всё или ничего

Найдите непрерывный участок массива с наибольшей суммой.

Если участков с наибольшей суммой несколько, выведите тот, у которого меньше номер начала; если и таких несколько — тот, у которого меньше номер конца.

Формат ввода

В первой строке nn от 11 до 21052 \cdot 10^5. Во второй — nn чисел, каждое по модулю не больше 10410^4.

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

Три числа: номер начала, номер конца и сама сумма. Нумерация с единицы.

Примеры

ввод
1
1
вывод
1 1 1
Войдите, чтобы отправлять решения.