Эта, на сегодняшний день простая задача была представлена студентам и школьникам для поступления на работу в Яндекс 2011 года, узнайте справились бы вы.

Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.

Входные данные В первой строке дано натуральное число n ( 1 ≤ n ≤ 10e5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10e4 .

Выходные данные Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.

5

-1 2 3 -2 5

2 5 8