Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Subsecuencia de suma mínima P95982

Statement

html

Dada una secuencia de n números enteros x₁ …x_n, calculad su subsecuencia consecutiva no vacía cuya suma sea más próxima a cero.

Entrada

La entrada tiene diversos casos. Cada caso empieza con n, seguido de n números enteros con valor absoluto no mayor que 10⁵.

Salida

Para cada caso, escribid el valor absoluto de la suma más próxima a cero, seguido de los índices izquierdo i y derecho d que delimitan la suma óptima x_i + … + x_d. Si hay más de una solución, escoged la i mínima. Si sigue el empate, escoged la d mínima.

Puntuación

test-1: 10 Puntos
Resolver casos como los del ejemplo 1, con 1 ≤ n ≤ 10, y con una sola subsecuencia de suma óptima.

test-2: Resolver casos como los del ejemplo 2, con 1 ≤ n ≤ 200. 20 Puntos

test-3: Resolver casos con 1 ≤ n ≤ 10⁴. 70 Puntos

Public test cases

Input

2   5 -4
1   -10
4   20 -9 3 4
3   1 0 2

Output

Input

4   0 0 0 0
6   10 -9 -2 -1 -3 2
3   1000 6 -1000

Output

0 1 1
1 1 2
6 1 3

Information

Author: Salvador Roura
Language: Spanish
Official solutions: C++
User solutions