Mediana dinàmica P37064

Statement

Donada una seqüència de paraules, escriviu la mediana de totes les paraules vistes a cada moment. Recordeu que la mediana d’un conjunt de $n$ elements és aquell que es trobaria a la posició $\lfloor (n + 1)/2 \rfloor$ si el conjunt estigués ordenat. Per exemple, la mediana de cinc elements és el tercer més petit, i la mediana de sis elements també és el tercer més petit.

Entrada

L’entrada consisteix en una seqüència de paraules minúscules diferents acabada en “END”.

Sortida

Per a cada paraula de l’entrada, escriviu la mediana de les paraules llegides fins al moment. Suposeu que les paraules s’ordenen en l’ordre alfabètic habitual.

Public test cases

Input

hola
bye
adeu
hi
hello
END

Output

hola
bye
bye
bye
hello

Input

a
b
c
d
e
f
END

Output

a
a
b
b
c
c

Input

f
e
d
c
b
a
END

Output

f
e
e
d
d
c

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++ Python
User solutions: C C++ Python