Границы выгодного отрезка

Найдите непустой кусок из подряд идущих элементов с наибольшей суммой и выведите его границы.

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

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Три числа через пробел: сумма, номер первого элемента и номер последнего. Нумерация с единицы.

К тому же проходу добавьте отметку, где начался текущий кусок: она меняется ровно тогда, когда кусок начинается заново. Условие «самый короткий из равных» проверяйте отдельно — оно не следует из самого алгоритма.