Median - MarisaOJ: Marisa Online Judge

Median

Time limit: 1000 ms
Memory limit: 256 MB
For an empty set $S$, you need to process $q$ queries: - `1 x`: If the set does not contain $x$ at this point, add the element $x$ to the set. Otherwise, remove $x$ from the set - `2`: Find the median in the set. If the elements are sorted in ascending order, and $n$ is the number of elements in the set, if $n$ is odd, the median is the element at index $\frac{n + 1}{2}$; if $n$ is even, the median is the average of the elements at indices $\frac{n}{2}$ and $\frac{n}{2} + 1$. The set $S$ at this point has at least one element. Index starts with $1$. ### Input - The first line contains an integer $q$. - The next $q$ lines, each containing a query in the specified format. ### Output - Print a number as the answer for each query of type $2$. If the answer is a real number, round it to one decimal place. ### Constraints - $1 \le q \le 10^5$. - $1 \le x \le 10^9$. ### Sample test Input ``` 8 1 5 2 1 6 2 1 5 1 8 1 10 2 ``` Output: ``` 5 5.5 8 ```