Спочатку послідовність порожня. Потрібно обробити q операцій. Кожна операція ADD x додати число x до послідовності. Після кожної операції потрібно вивести медіану всіх чисел.

Input Specification

Перший рядок містить ціле число \(q\), де \(q\) --- кількість запитів. Наступні \(q\) рядків містять запити \(ADD\: x\), де \(ADD\: x\) --- запит(\(x\) --- ціле число). \(\\1 \leq q \leq 2 \cdot 10^5\\\) \(-10^9 \leq x \leq 10^9\\\)

Output Specification

Після кожної операції вивести медіану.

Sample Input 1

3
ADD 5
ADD 2
ADD 8

Sample Output 1

5
2
5

Sample Input 2

5
ADD 5
ADD 2
ADD 8
ADD 1
ADD 10

Sample Output 2

5
2
5
2
5