Racha afortunada
Vladimir es un jugador de póquer profesional que lleva muchos años perfeccionando su técnica de juego. Sabe que la práctica y la constancia son la clave para llegar a dominar cualquier cosa y, desde el principio, lleva registros exhaustivos de todas sus partidas.
Como todos los jugadores, tiene días mejores y días peores. Forma parte del juego, a veces se gana y a veces se pierde. Sin embargo, mirando sus registros se ha dado cuenta de que a veces tiene rachas muy buenas en las que gana casi siempre y le gustaría identificarlas.
En particular, teniendo en cuenta las ganancias o pérdidas de cada día, le gustaría conocer qué día debería haber empezado a jugar y qué día debería haberlo dejado para maximizar sus ganancias, suponiendo que jugase todos los días intermedios. ¿Puedes ayudarle?
Entrada
El primer número de la entrada indica el número de casos de prueba que aparecen a continuación.
Cada caso de prueba está compuesto por dos líneas. La primera contiene el número de días anotados en el registro (al menos 1 y como mucho 100.000), y la segunda línea las ganancias (números positivos) o pérdidas (números negativos) de cada día. Cuando las ganancias o las pérdidas de un día llegan a 10.000, lo deja antes de que la suerte le abandone, o de que tenga que volver a casa desnudo tapándose con un barril.
Salida
Para cada caso de prueba se deberá imprimir una línea con dos números que delimitan el intervalo de días consecutivos que Vladimir debería haber jugado para maximizar sus ganancias (suponiendo que sólo jugase esos días). Ten en cuenta que Vladimir juega tanto el día de inicio como el día de fin del intervalo, y que los días empiezan a numerarse en 1.
En caso de existir varios intervalos en los que Vladimir podría obtener el máximo beneficio posible, se debe elegir el de duración más corta y, a igualdad de duración, el que empiece primero. Al fin y al cabo, a nadie le gusta trabajar más de lo necesario y todos preferimos terminar cuanto antes.
Vladimir es un profesional, por lo que siempre hay al menos un día en el que gana algo.
Entrada de ejemplo
3 4 -10 4 8 -2 5 -3 0 7 -20 -7 11 30 -7 1 -25 -20 25 10 3 -1 8 -100
Salida de ejemplo
2 3 3 3 6 10