Mediana P81824

Dada una secuencia de palabras, escribid en cada momento la mediana de las palabras leídas. Recordad que la mediana de un conjunto de $n$ elementos es aquel que se encontraría en la posición $\lfloor (n + 1)/2 \rfloor$ si el conjunto estuviese ordenado. Así, la mediana de cinco elementos es el tercero más pequeño, y la mediana de seis elementos también es el tercero más pequeño.

Entrada

La entrada consiste en una secuencia no vacía de palabras minúsculas acabada en ‘FIN’. Las palabras son todas diferentes entre sí, y tienen entre una y diez letras minúsculas.

Salida

Para cada palabra de la entrada, escribid en una línia la mediana del conjunto de palabras leídas hasta el momento. Suponed que las palabras se ordenan entre sí, como es habitual, en orden alfabético.

Puntuación

• TestA:   Resolver entradas con hasta 2 palabras.

• TestA:   Resolver entradas con hasta 5 palabras.

• TestA:   Resolver entradas con hasta 100 palabras.

• TestA:   Resolver entradas con hasta 2000 palabras.

• TestA:   Resolver entradas con hasta 50000 palabras.