Problem Description

Design a data structure that supports adding integers and finding the median of all added numbers efficiently. The median is the middle value in a sorted list, or the average of two middle values for even-length lists.

Input Format

First line contains n (number of operations). Next n lines contain either "ADD x" (add integer x) or "MEDIAN" (get current median).

Output Format

For each MEDIAN operation, output the median as a decimal number (1 decimal place).

Constraints

• 1 ≤ n ≤ 10000

• -10000 ≤ integers ≤ 10000

• At least one ADD before first MEDIAN

• Output median with exactly 1 decimal place

• Use efficient data structure (heaps recommended)

Sample Input/Output

7
ADD 1
ADD 2
MEDIAN
ADD 3
MEDIAN
ADD 4
MEDIAN

1.5
2.0
2.5

Explanation

After adding 1,2: median = (1+2)/2 = 1.5. After adding 3: sorted=[1,2,3], median = 2.0. After adding 4: sorted=[1,2,3,4], median = (2+3)/2 = 2.5.