Llegan números de a uno y en cualquier momento te pueden pedir la mediana de los que han llegado: si hay una cantidad impar, el del medio al ordenarlos; si es par, el promedio de los dos del medio.

• add x: llega el número \(x\).
• median: imprime la mediana actual.

Entrada

La primera línea tiene \(q\) \((1 \le q \le 10^5)\) y siguen \(q\) líneas con una operación cada una \((|x| \le 10^5)\). median solo aparece cuando ya llegó al menos un número.

Salida

Una línea por cada median. Se acepta un error absoluto o relativo de hasta \(10^{-5}\) (por ejemplo, 2.5, 2.50000 o 3 y 3.0).

Ejemplo 1

Entrada

5
add 1
add 2
median
add 3
median

Salida

1.5
2.0

Ejemplo 2

Entrada

4
add -5
median
add -2
median

Salida

-5.0
-3.5

Basado en el problema 295 de LeetCode, Find Median from Data Stream, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.