Subsecuencia de suma mínima P95982

Statement

Dada una secuencia de $n$ números enteros $x_1$ … $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^5$ .

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 + \dots + 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:

Resolver casos como los del ejemplo 1, con $1 \le n \le 10$ , y con una sola subsecuencia de suma óptima.

test-2: Resolver casos como los del ejemplo 2, con $1 \le n \le 200$ .

test-3: Resolver casos con $1 \le n \le 10^4$ .

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: C++