Shoes Again
ПрАнКА 2010
Time Limit: 0.2s, Memory Limit: 64MiB
Когато Ели пазарува, го прави със замах. Нейните шопинг терапии опразват почти целия мол, който тя си е харесала. В следствие на това, Българската Асоциация на Моловете, Базарите и Илиeнци, накратко БАМБИ, решиха да й направят мръсно и построиха Mall Serdika.

Ели се готви за контра-атака и решава да оптимизира своето пазаруване. Влизайки в произволен магазин, тя отива пред най-дългия рафт или витрина, разглежда стоките там (които ще считаме за наредени в редичка), определя колко й харесва всяка от тях, и купува цял под-интервал. Разбира се, момичето избира този под-интервал, чиито стоки сумарно й харесват най-много.

Например, ако тя си избере интервала [2, 5], това означава, че тя ще вземе втората, третата, четврътата и петата стока в редицата, като общото удовлетворение за Ели е сумата на това колко й харесва всяка от тях.

Някои от продуктите по магазините получават и отрицателна оценка – например тениска на Кристиано Роналдо или футболни обувки не са неща, което тя би носила. Също така, влизайки в някоя книжарница, от време на време сред интересните книги като Хари Потър и Twilight се нареждат и такива като „Програмиране = ++алгоритми”. Кой би чел нещо такова!?

Помогнете на Ели, като напишете програма, която при дадена оценка на всяка от стоките в редичката, намира интервала от стоки, който би й донесъл най-голямо удовлетворение.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броят стоки на рафта или витрината. На следващия ред ще има N цели числа A1, A2, …, AN – оценката на всяка от стоките, в реда, в който са изложени.
Изход
На единствен ред на стандартния изход изведете три цели числа – най-голямата сума от последователни стоки, която Ели може да получи, следвана от индексите на най-лявата и най-дясната стока. Ако съществува повече от един оптимален интервал, изпечатайте този, който започва най-отляво. Ако отново има няколко възможности, изведете най-късия от тях. Индексирането на стоките започва от 1.
Ограничения
  • 1 ≤ N ≤ 100,000
  • -1,000,000 ≤ Ai ≤ 1,000,000
Примерен Вход Примерен Изход
8 2 5 -1 3 -3 -7 4 2 9 1 4
18 -2 4 4 4 4 0 -5 1 -5 1 -5 1 -5 1 -5 8 8 -2 16 2 5
В първия тест е най-изгодно за Ели да вземе 2 + 5 + (-1) + 3 = 9 – тоест числата от 1-ва до 4-та позиция. Във втория имаме 3 интервала, които дават максималната оценка 16 – това са [2, 5], [2, 6] и [16, 17]. Tези, които започват от най-левия елемент са [2, 5] и [2, 6]. По-късият от тях е [2, 5].
Мрън!