Farmer Johns langer Zaun hat Pfosten und Riegel. $N$ ($1 \le N \le 3000$) Pfosten tragen Zahlen $-1000$ bis $+1000$, Wiederholungen möglich. Beim Wiederkäuen erfinden Kühe ein Spiel: „beste Zaunsumme“ gewinnt Eis zum Nachtisch.

Gesucht ist die längste zusammenhängende Pfostenfolge unter denen mit kleinstem Summenbetrag. Finde die Gewinnersumme.

Eingabe

• Zeile 1: ganze Zahl $N$.

• Zeilen $2..N+1$: Pfostenwerte, Zeile 2 Nummer 1 usw.

Ausgabe

Eine Zeile, drei Zahlen:

• Nummer des ersten summierten Pfostens,

• Nummer des letzten summierten Pfostens,

• Betrag der Summe. Gleiche beste Summe und maximale Länge: kleinste Anfangsnummer.

Beispiele

Eingabe 1

6
5
10
-5
-6
2
4

Ausgabe 1

4 6 0

Autor: Dominic Battre, 2001