Longue clôture de Farmer John, poteaux et traverses. $N$ ($1 \le N \le 3000$) poteaux étiquetés de $-1000$ à $+1000$, répétitions possibles. En ruminant, les vaches jouent : trouver la « meilleure somme » donne une glace en dessert.

Il faut la plus longue suite contiguë parmi celles à valeur absolue minimale de somme. Trouvez la somme gagnante.

Entrée

• Ligne 1 : entier $N$.

• Lignes $2..N+1$ : étiquettes, ligne 2 poteau 1, etc.

Sortie

Une ligne, trois nombres :

• Numéro du premier poteau sommé,

• Numéro du dernier poteau sommé,

• Valeur absolue de la somme. Si meilleure somme et longueur maximale égales, choisir le plus petit numéro initial.

Exemples

Entrée 1

6
5
10
-5
-6
2
4

Sortie 1

4 6 0

Auteur : Dominic Battre, 2001