Median - MarisaOJ: Marisa Online Judge

For an empty set

S

$S$ , you need to process

q

$q$ queries: -

1 x

$1 x$ : If the set does not contain

x

$x$ at this point, add the element

x

$x$ to the set. Otherwise, remove

x

$x$ from the set -

2

$2$ : Find the median in the set. If the elements are sorted in ascending order, and

n

$n$ is the number of elements in the set, if

n

$n$ is odd, the median is the element at index

\frac{n + 1}{2}

$\frac{n + 1}{2}$ ; if

n

$n$ is even, the median is the average of the elements at indices

\frac{n}{2}

$\frac{n}{2}$ and

\frac{n}{2} + 1

$\frac{n}{2} + 1$ . The set

S

$S$ at this point has at least one element. Index starts with

1

$1$ . ### Input - The first line contains an integer

q

$q$ . - The next

q

$q$ lines, each containing a query in the specified format. ### Output - Print a number as the answer for each query of type

2

$2$ . If the answer is a real number, round it to one decimal place. ### Constraints -

1 \leq q \leq 10^{5}

$1 \le q \le 10^5$ . -

1 \leq x \leq 10^{9}

$1 \le x \le 10^9$ . ### Sample test Input

815216215181102

$8 1 5 2 1 6 2 1 5 1 8 1 10 2$

Output:

5 5.5 8

$5 5.5 8$

Topic

STL

Rating

1200

Solution (0)

Solution