Problema número 271

Pájaros en vuelo

Tiempo máximo: 3,000-4,000 sMemoria máxima: 16384 KiB
Bandada de pájaros

Es muy conocido que algunas especies de aves vuelan creando una formación en V. La razón es simple: de esa forma las aves que van detrás aprovechan el rebufo de las que van delante. Esto implica que el pájaro que hace más esfuerzo es aquél que va primero ocupando el vértice de la V, por lo que es importante elegir bien quién es.

Algunas especies lo que hacen es colocarse en orden de edad de izquierda a derecha, de forma que el pájaro que queda en el centro es el que no es ni demasiado joven ni demasiado viejo. De esta forma evitan que el que abre camino esté poco desarrollado o demasiado cansado para tirar del grupo. Cuando a la bandada se van uniendo más pájaros, ocupan su lugar y, si es necesario, el pájaro que abre el camino cambia.

Por ejemplo, imaginemos que hay una bandada en vuelo con pájaros de edades 10, 20 y 30 meses. En ese caso, el que ocupará el primer lugar es el de 20 meses. Si ahora llegan dos pájaros nuevos, uno de 25 meses y otro de 35, ambos ocuparán su sitio y el primero pasará a ser el de 25 meses. Si posteriormente llega un abuelo de 40 meses con su nieto de 5, ocuparán los extremos y el primer puesto no variará.

Lo que queremos es simular la formación de una de estas bandadas de pájaros que comienza con un único ejemplar y a la que se van añadiendo nuevas parejas. Cada vez que se añade una pareja queremos determinar la edad del ave que ocupa la punta de la bandada.

Entrada

La entrada estará compuesta por una serie de casos de prueba, cada uno con la información de creación de una bandada de pájaros. Cada caso consta de dos líneas: la primera contiene la edad del primer pájaro que echa a volar seguido del número de parejas que se irán uniendo después (al menos una y hasta 100.000 parejas); en la línea siguiente aparecen las edades de cada pareja.

Se garantiza que las edades de cada uno de los pájaros que entran en la bandada son distintas. Para eso éstas vienen expresadas en segundos, y nunca será un número mayor a 100.000.000.

La entrada termina con una línea con dos ceros.

Salida

Para cada caso de prueba se escribirá una línea que tendrá tantos números como parejas se incorporan a la bandada, indicando la edad del pájaro que ocupa la primera posición tras la incorporación de cada pareja.

Entrada de ejemplo

30 3
10 20 35 25 5 40
0 0

Salida de ejemplo

20 25 25