Opis

Mediana (inaczej: wartość środkowa) to w statystyce wartość cechy w ciągu uporządkowanym, powyżej i poniżej której znajduje się jednakowa liczba obserwacji.
Aby obliczyć medianę ze zbioru n obserwacji, sortujemy je niemalejąco i numerujemy od 1 do n. Następnie, jeśli n jest nieparzyste, medianą jest wartość obserwacji w środku (czyli obserwacji numer (n+1)/2). Jeśli natomiast n jest parzyste, medianą jest średnia arytmetyczna między dwiema środkowymi obserwacjami (czyli obserwacją numer n/2 i obserwacją numer n/2+1).
Przykład
Mediana ciągu 1 2 2 3 4 8 10 jest równa 3.
Mediana ciągu 1 2 2 3 4 8 10 20 jest równa 3,5.

Wejście

Ciąg liczb całkowitych, po jednej w każdej linii. Wszystkich liczb będzie nie więcej niż 10000.

Wyjście

Ciąg liczb całkowitych, po jednej w każdej linii. Wartości powinno być tyle samo ile liczb na wejściu. i-ta liczba oznacza medianę ciągu złożonego z wczytanych liczb od pierwszej do i-tej. Innymi słowy, po wczytaniu każdej kolejnej liczby program powinien wydrukować na wyjście medianę ciągu wczytanego do tego czasu. Jeśli otrzymana mediana nie jest liczbą całkowitą, program powinien wypisać tylko jej część całkowitą.

Przykład

Wejście

1
3
4
60
70
50
2

Wyjście

1
2
3
3
4
27
4