Programacion Competitiva Bolivia

Un analista está estudiando los comportamientos mensuales de diversas empresas desde un año base. Desea averiguar las meses cuando a las empresas les fue mejor, pero para ello debe averiguar el periodo de tiempo (desde que mes hasta que mes) cuando les fue mejor.

Las ganancias que obtuvo se están expresadas como un números enteros. Se desea conocer cual fue el periodo (mes de inicio y mes de finalización) de ganancia máxima, y el numero de meses que representa este periodo.

Por ejemplo:

+----------+---+-----+---+----+-----+---+----+-----+-----+----+
| Mes      | 0 |   1 | 2 |  3 |   4 | 5 |  6 |   7 |   8 |  9 |
| Utilidad | 5 | -15 | 7 | 18 | -10 | 9 | 10 | -25 | -15 | 20 |
+----------+---+-----+---+----+-----+---+----+-----+-----+----+

En este ejemplo el periodo que obtuvo la máxima ganancia es: del mes 2 al mes 6 con una ganancia de 34

Dados M datos, númerados entre el mes 0 y el mes M − 1.

Entrada

La entrada consiste de varios datos de prueba y termina cuando no hay más datos. La primera línea de un caso de prueba es la cantidad de meses (1 ≤ M ≤ 10⁶) a evaluar. La siguiente linea tiene M números enteros separados por un espacio con valores entre -100 y 100.

La entrada termina cuando M = 0.

Salida

En la salida escriba la ganancia máxima, el mes de inicio y finalización del périodo de ganancia máxima.

Es posible de que existan multiples soluciones óptimas, si este fuera el caso, imprimir la que tenga el mes de finalización mayor y si aún existiera empate, imprimir la que tenga el periodo más corto.

Si la ganancia máxima es un número no positivo, imprimir 0 -1 -1.

+--------------------------------+--------------------+
|      Ejemplos de entrada       | Ejemplos de salida |
+--------------------------------+--------------------+
| 10                             | 34 2 6             |
| 5 -15 7 18 -10 9 10 -25 -15 20 | 10 0 0             |
| 1                              | 0 -1 -1            |
| 10                             |                    |
| 2                              |                    |
| -15 -5                         |                    |
| 0                              |                    |
+--------------------------------+--------------------+