The median of $\mbox{M}$ numbers is defined as the middle number after sorting them in order if $\mbox{M}$ is odd. Or it is the average of the middle two numbers if $\mbox{M}$ is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median.

Example: 

For a set of $M=5$ numbers $9,2,8,4,1$ the median is the third number in the sorted set $1,2,4,8,9$, which is $\begin{array}{c}4\end{array}$. Similarly, for a set of $M=4$ numbers, $5,2,10,4$, the median is the average of the second and the third element in the sorted set $2,4,5,10$, which is $(4+5)/2=4.5$.  

Input: 

The first line is an integer, $N$, that indicates the number of operations. Each of the next $N$ lines is either a x or r x. a x indicates that $\boldsymbol{x}$ is added to the set, and r x indicates that $\boldsymbol{x}$ is removed from the set.

Output: 

For each operation: If the operation is add, output the median after adding $\boldsymbol{x}$ in a single line. If the operation is remove and the number $\boldsymbol{x}$ is not in the list, output Wrong! in a single line. If the operation is remove and the number $\boldsymbol{x}$ is in the list, output the median after deleting $\boldsymbol{x}$ in a single line. (If the result is an integer DO NOT output decimal point. And if the result is a real number, DO NOT output trailing 0s.)

Note 

If your median is 3.0, print only 3. And if your median is 3.50, print only 3.5. Whenever you need to print the median and the list is empty, print Wrong!

Constraints: 

$0<N\leq10^5$


For each a x or r x, $\boldsymbol{x}$ will always be a signed integer (which will fit in 32 bits).

Sample Input:  

7  
r 1  
a 1  
a 2  
a 1  
r 1  
r 2  
r 1  

Sample Output:  

Wrong!  
1  
1.5  
1  
1.5  
1  
Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty, you have to print Wrong!.
$$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Tree queries


Solutions:
from bisect import bisect_left

class MedianFinder:

	def __init__(self):
		self.items = []

	def addItem(self, num):
		position = bisect_left(self.items, num)
		self.items.insert(position, num)
		return self.median()

	def remItem(self, num):
		position = bisect_left(self.items, num)
		if position >= len(self.items) or self.items[position] != num:
			return 'Wrong!'
		else:
			del self.items[position]
			return self.median()

	def median(self):
		l = len(self.items)
		if l == 0:
			return 'Wrong!'
		elif l & 1:
			return self.items[int(l / 2)]
		else:
			ans = self.items[int(l / 2)] + self.items[int(l / 2) - 1]
			if ans == 0:
				return 0
			elif ans & 1:
				return ans / 2
			else:
				return int(ans / 2)
N = int(input())
arr = MedianFinder()
for i in range(N):
	Q = input().split(' ')
	num = int(Q[1])
	if Q[0] == 'a':
		print(arr.addItem(num))
	elif Q[0] == 'r':
		print(arr.remItem(num))


import sys
from bisect import insort_left, bisect_left

def ops(lines=sys.stdin):
	next(lines)
	for line in sys.stdin:
		(op, n) = line.split()
		yield (op, int(n))

def running_median(ops):
	numbers = []
	for (op, n) in ops:
		if op == 'a':
			insort_left(numbers, n)
		else:
			i = bisect_left(numbers, n)
			if i < len(numbers) and numbers[i] == n:
				del numbers[i]
			else:
				yield 'Wrong!'
				continue
			if not numbers:
				yield 'Wrong!'
				continue
		l = len(numbers)
		if l % 2:
			yield numbers[l // 2]
		else:
			m = sum(numbers[int(l / 2) - 1:int(l / 2) + 1]) / 2
			if m % 1 == 0:
				yield int(m)
			else:
				yield m
for median in running_median(ops()):
	print(median)


array = []

def calcMedian():
	sz = len(array)
	if sz == 0:
		print('Wrong!')
	elif sz % 2 == 0:
		v = (array[sz // 2 - 1] + array[sz // 2]) / 2
		if int(v) == v:
			print(int(v))
		else:
			print(v)
	else:
		v = array[(sz - 1) // 2]
		if int(v) == v:
			print(int(v))
		else:
			print(v)

def rem(l, u, x):
	if l > u:
		return False
	else:
		m = (l + u + 1) // 2
		if array[m] == x:
			del array[m]
			return True
		elif array[m] < x:
			return rem(m + 1, u, x)
		else:
			return rem(l, m - 1, x)

def ins(l, u, x):
	if l == u:
		array.insert(u, x)
	else:
		m = (l + u) // 2
		if array[m] == x:
			array.insert(m, x)
		elif array[m] < x:
			ins(m + 1, u, x)
		else:
			ins(l, m, x)
n = int(input())
for i in range(0, n):
	arr = input().split(' ')
	x = int(arr[1])
	if arr[0] == 'r':
		if rem(0, len(array) - 1, x):
			calcMedian()
		else:
			print('Wrong!')
	else:
		if len(array) == 0:
			array += [x]
		else:
			ins(0, len(array), x)
		calcMedian()


def insertNumber(array, number):
	if not array:
		array.append(number)
		return
	if len(array) == 1:
		if number > array[0]:
			array.append(number)
		else:
			array.insert(0, number)
		return
	si = 0
	ei = len(array) - 1
	binarySearchInsert(array, number, si, ei)

def binarySearchInsert(array, number, si, ei):
	if si == ei:
		if number > array[si]:
			array.insert(si + 1, number)
			return
		else:
			array.insert(si, number)
			return
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			binarySearchInsert(array, number, middle + 1, ei)
		elif number < array[middle]:
			binarySearchInsert(array, number, si, middle)
		else:
			array.insert(middle, number)
			return

def removeNumber(array, number):
	if not array:
		return False
	if len(array) == 1:
		if number == array[0]:
			array.pop()
			return True
		else:
			return False
	si = 0
	ei = len(array) - 1
	return binarySearchRemove(array, number, si, ei)

def binarySearchRemove(array, number, si, ei):
	if si == ei:
		if number == array[si]:
			array.pop(si)
			return True
		else:
			return False
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearchRemove(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearchRemove(array, number, si, middle)
		else:
			array.pop(middle)
			return True

def printMedian(nl):
	length = len(nl)
	if length == 0:
		print('Wrong!')
	else:
		if length % 2 == 1:
			index = length // 2
			median = nl[index]
		else:
			index1 = length // 2 - 1
			index2 = length // 2
			median = (nl[index1] + nl[index2]) / 2
		if int(median) == median:
			print(int(median))
		else:
			print(median)
n = int(input().strip())
nl = []
for op in range(n):
	operation = input().split(' ')
	if operation[0] == 'a':
		insertNumber(nl, int(operation[1]))
	elif not removeNumber(nl, int(operation[1])):
		print('Wrong!')
		continue
	printMedian(nl)


def binary_search(a, x, lo=0, hi=None):
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		midval = a[mid]
		if midval < x:
			lo = mid + 1
		elif midval > x:
			hi = mid
		else:
			return mid
	return -1

def binary_search1(a, x, lo=0, hi=None):
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		midval = a[mid]
		if midval < x:
			lo = mid + 1
		elif midval > x:
			hi = mid
		else:
			return mid
	return lo
n = input('')
l = []
for i in range(0, int(n)):
	d = input('')
	m = d.split()
	s = m[0]
	num = int(m[1])
	if s is 'r':
		k = binary_search(l, num, 0, len(l))
		if k == -1:
			print('Wrong!')
		else:
			del l[k]
			if len(l) == 0:
				print('Wrong!')
			elif len(l) % 2 == 0:
				sol = (l[int(len(l) / 2)] + l[int(len(l) / 2) - 1]) / 2
				if int(sol) == sol:
					print(int(sol))
				else:
					print((l[int(len(l) / 2)] + l[int(len(l) / 2) - 1]) / 2)
			else:
				print(l[int(len(l) / 2)])
	elif s is 'a':
		k = binary_search1(l, num, 0, len(l))
		l.insert(k, num)
		if len(l) % 2 == 0:
			sol = (l[int(len(l) / 2)] + l[int(len(l) / 2) - 1]) / 2
			if int(sol) == sol:
				print(int(sol))
			else:
				print((l[int(len(l) / 2)] + l[int(len(l) / 2) - 1]) / 2)
		else:
			print(l[int(len(l) / 2)])


def insertNumber(array, number):
	if not array:
		array.append(number)
		return
	if len(array) == 1:
		if number > array[0]:
			array.append(number)
		else:
			array.insert(0, number)
		return
	si = 0
	ei = len(array) - 1
	binarySearchInsert(array, number, si, ei)

def binarySearchInsert(array, number, si, ei):
	if si == ei:
		if number > array[si]:
			array.insert(si + 1, number)
			return
		else:
			array.insert(si, number)
			return
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			binarySearchInsert(array, number, middle + 1, ei)
		elif number < array[middle]:
			binarySearchInsert(array, number, si, middle)
		else:
			array.insert(middle, number)
			return

def removeNumber(array, number):
	if not array:
		return False
	if len(array) == 1:
		if number == array[0]:
			array.pop()
			return True
		else:
			return False
	si = 0
	ei = len(array) - 1
	return binarySearchRemove(array, number, si, ei)

def binarySearchRemove(array, number, si, ei):
	if si == ei:
		if number == array[si]:
			array.pop(si)
			return True
		else:
			return False
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearchRemove(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearchRemove(array, number, si, middle)
		else:
			array.pop(middle)
			return True

def printMedian(nl):
	length = len(nl)
	if length == 0:
		print('Wrong!')
	else:
		if length % 2 == 1:
			index = length // 2
			median = nl[index]
		else:
			index1 = length // 2 - 1
			index2 = length // 2
			median = (nl[index1] + nl[index2]) / 2
		if int(median) == median:
			print(int(median))
		else:
			print(median)
n = int(input().strip())
nl = []
for op in range(n):
	operation = input().split(' ')
	if operation[0] == 'a':
		insertNumber(nl, int(operation[1]))
	elif not removeNumber(nl, int(operation[1])):
		print('Wrong!')
		continue
	printMedian(nl)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().strip().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


N = int(input())
commands = [input().split() for i in range(N)]
nums = []

def output(x):
	if x % 1 == 0:
		print(int(x))
	else:
		print(x)
import bisect
for com in commands:
	if com[0] == 'a':
		bisect.insort(nums, int(com[1]))
	elif com[0] == 'r':
		try:
			del nums[nums.index(int(com[1]))]
		except:
			print('Wrong!')
			continue
	try:
		if len(nums) % 2 == 0:
			output((nums[int(len(nums) / 2) - 1] + nums[int(len(nums) / 2)]) / 2)
		else:
			output(nums[int((len(nums) - 1) / 2)])
	except:
		print('Wrong!')


def median(x):
	leng = len(x)
	if len(x) % 2 == 1:
		print(x[leng // 2])
	elif leng == 0:
		print('Wrong!')
	else:
		y = (x[leng // 2 - 1] + x[leng // 2]) / 2
		if y == int(y):
			print(int(y))
		else:
			print(y)

def linear(lis, elem, r1, r2):
	for i in range(r1, r2 + 1):
		if lis[i] >= elem:
			lis.insert(i, elem)
			return
	lis.insert(r2 + 1, elem)

def binaryInsert(lis, elem):
	if len(lis) == 0:
		lis.append(elem)
		return
	lower = 0
	upper = len(lis) - 1
	while upper - lower > 2:
		median = (lower + upper) // 2
		if lis[median] > elem:
			upper = median
		elif lis[median] < elem:
			lower = median
		else:
			lower = median
			upper = median
			break
	linear(lis, elem, lower, upper)
x = int(input())
masterList = []
for i in range(x):
	h = input()
	h = h.split()
	y = int(h[1])
	if h[0] == 'a':
		binaryInsert(masterList, y)
		median(masterList)
	if h[0] == 'r':
		try:
			masterList.remove(y)
			median(masterList)
		except ValueError:
			print('Wrong!')


from bisect import insort

def mutate(nums, o, n):
	if o == 'r':
		try:
			idx = nums.index(n)
		except:
			return False
		nums.pop(idx)
		if len(nums) == 0:
			return False
		return True
	elif o == 'a':
		insort(nums, n)
		return True

def calc_median(nums):
	l = len(nums)
	m = l // 2
	if bool(l % 2):
		return nums[m]
	else:
		val = (nums[m - 1] + nums[m]) / 2
		if isinstance(val, float) and val.is_integer():
			return int(val)
		return val

def median(a, x, l):
	li = []
	for i in range(l):
		operation = a[i]
		num = x[i]
		mut = mutate(li, operation, num)
		if not mut:
			print('Wrong!')
			continue
		print(calc_median(li))
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x, N)


import sys
from bisect import insort
wrong = 'Wrong!'
opnum = int(sys.stdin.readline())
numbers = list()

def append(num):
	insort(numbers, num)

def remove(num):
	numbers.remove(num)
for iz in range(opnum):
	input = sys.stdin.readline()
	op = input[:1]
	num = int(input[1:])
	try:
		if op == 'a':
			append(num)
		else:
			remove(num)
		lng = len(numbers)
		if lng == 0:
			raise
		h = lng // 2
		if lng & 1:
			print(numbers[h])
		else:
			summ = sum(numbers[h - 1:h + 1])
			if summ & 1:
				print(summ / 2)
			else:
				print(summ // 2)
	except:
		print(wrong)


from bisect import *

def median(x):
	if len(x) == 0:
		print('Wrong!')
	elif len(x) % 2 == 1:
		print(x[int(len(x) / 2)])
	else:
		index = int(len(x) / 2)
		print(('%f' % ((x[index - 1] + x[index]) / 2)).rstrip('0').rstrip('.'))
N = int(input())
x = []
for i in range(N):
	tmp = input().strip().split()
	(a, b) = [xx for xx in tmp]
	b = int(b)
	if a == 'a':
		insort_left(x, b)
		median(x)
	else:
		try:
			x.remove(b)
			median(x)
		except ValueError:
			print('Wrong!')


import sys
import bisect

def median(lst):
	if len(lst) % 2 == 1:
		return lst[len(lst) // 2]
	elif (lst[len(lst) // 2] + lst[len(lst) // 2 - 1]) / 2 % 1 == 0:
		return (lst[len(lst) // 2] + lst[len(lst) // 2 - 1]) // 2
	else:
		return (lst[len(lst) // 2] + lst[len(lst) // 2 - 1]) / 2

def main():
	n = int(sys.stdin.readline())
	nums = []
	for _ in range(n):
		(stat, num) = sys.stdin.readline().split()
		num = int(num)
		if stat == 'r':
			if num not in nums:
				print('Wrong!')
				continue
			else:
				nums.remove(num)
		elif stat == 'a':
			bisect.insort_left(nums, num)
		if len(nums) == 0:
			print('Wrong!')
		else:
			print(median(nums))
main()


def median(ops, nums):
	buf = []
	for (op, n) in zip(ops, nums):
		if op == 'a':
			insert(buf, n)
		elif op == 'r':
			try:
				buf.remove(n)
				if not buf:
					print('Wrong!')
					continue
			except ValueError:
				print('Wrong!')
				continue
		last = len(buf) - 1
		if last % 2 == 0:
			m = buf[last // 2]
		else:
			m = (buf[last // 2] + buf[last // 2 + 1]) / 2
			if int(m) == m:
				m = int(m)
		print(m)

def find(ar, e):
	(i, j, m) = (0, len(ar) - 1, 0)
	while i <= j:
		m = (i + j) // 2
		if e > ar[m]:
			i = m + 1
		elif e < ar[m]:
			j = m - 1
		else:
			return m
	return m

def insert(ar, e):
	if not ar:
		ar.append(e)
	else:
		idx = find(ar, e)
		if e > ar[idx]:
			ar.insert(idx + 1, e)
		else:
			ar.insert(idx, e)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import math

class Heap:

	def __init__(self, order):
		self.heap = [0]
		self.size = 0
		self.heapMap = {}
		self.order = order

	def __len__(self):
		return self.size

	def __contains__(self, x):
		return x in self.heapMap

	def top(self):
		return self.heap[1]

	def swapPosition(self, x, p, q):
		self.heapMap[x].remove(p)
		self.heapMap[x].add(q)

	def heapify(self, startpos):
		(v, p) = (startpos, startpos // 2)
		while p:
			if self.order(self.heap[p], self.heap[v]):
				break
			(self.heap[p], self.heap[v]) = (self.heap[v], self.heap[p])
			self.swapPosition(self.heap[p], v, p)
			self.swapPosition(self.heap[v], p, v)
			(v, p) = (p, p // 2)

	def add(self, x):
		self.heap.append(x)
		self.size += 1
		if x not in self:
			self.heapMap[x] = set()
		self.heapMap[x].add(self.size)
		self.heapify(self.size)

	def remove(self, x):
		if 1 not in self.heapMap[x]:
			pos = self.heapMap[x].pop()
			if not self.heapMap[x]:
				del self.heapMap[x]
			self.heap[pos] = self.heap[1]
			self.heapMap[self.heap[1]].add(pos)
			self.heapify(pos)
		(self.heap[1], self.heap[-1]) = (self.heap[-1], self.heap[1])
		if self.heap[1] != self.heap[-1]:
			self.swapPosition(self.heap[1], self.size, 1)
			self.swapPosition(self.heap[-1], 1, self.size)
		self.heapMap[self.heap[-1]].remove(self.size)
		if not self.heapMap[self.heap[-1]]:
			del self.heapMap[self.heap[-1]]
		self.size -= 1
		del self.heap[-1]
		(p, v) = (1, 1 * 2)
		while v <= self.size:
			child = p
			if not self.order(self.heap[child], self.heap[v]):
				child = v
			if v + 1 <= self.size and (not self.order(self.heap[child], self.heap[v + 1])):
				child = v + 1
			if child == p:
				break
			(self.heap[p], self.heap[child]) = (self.heap[child], self.heap[p])
			self.swapPosition(self.heap[p], child, p)
			self.swapPosition(self.heap[child], p, child)
			(p, v) = (child, child * 2)

def median(actions):
	(maxHeap, minHeap) = (Heap(lambda x, y: x >= y), Heap(lambda x, y: x <= y))

	def getMedian():
		if not len(maxHeap):
			return 'Wrong!'
		median = maxHeap.top()
		if len(minHeap) == len(maxHeap):
			median = (median + minHeap.top()) / 2
		if math.floor(median) == median:
			median = int(median)
		return median

	def balance():
		if len(maxHeap) - len(minHeap) > 1:
			top = maxHeap.top()
			maxHeap.remove(top)
			minHeap.add(top)
		elif len(maxHeap) < len(minHeap):
			top = minHeap.top()
			minHeap.remove(top)
			maxHeap.add(top)
	for (a, x) in actions:
		if a == 'a':
			if len(minHeap) and x >= minHeap.top():
				minHeap.add(x)
			else:
				maxHeap.add(x)
			balance()
			print(getMedian())
		elif x in maxHeap:
			maxHeap.remove(x)
			balance()
			print(getMedian())
		elif x in minHeap:
			minHeap.remove(x)
			balance()
			print(getMedian())
		else:
			print('Wrong!')
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(zip(s, x))


import sys, math, copy
data = sys.stdin.readlines()
from bisect import bisect_left

def parse(line):
	(o, n) = line.split()
	return (o, int(n))
ops = [parse(line) for line in data[1:]]
c = 0
a = []
for (op, n) in ops:
	if op == 'a':
		i = bisect_left(a, n) if a else 0
		a.insert(i, n)
		c += 1
	elif op == 'r':
		if n in a:
			i = bisect_left(a, n)
			a.pop(i)
			c -= 1
		else:
			print('Wrong!')
			continue
	if c:
		im = (c - 1) // 2
		if c % 2:
			m = a[im]
			print(m)
		else:
			m = (a[im] + a[im + 1]) / 2
			mi = int(m)
			if abs(m - mi) > 0.2:
				print(m)
			else:
				print(mi)
	else:
		print('Wrong!')


import bisect

def median(a, x):
	lst = []
	for i in range(len(a)):
		if a[i] == 'a':
			bisect.insort_left(lst, x[i])
			if len(lst) % 2 == 1:
				print(lst[len(lst) // 2])
			else:
				average = (lst[len(lst) // 2] + lst[len(lst) // 2 - 1]) / 2.0
				print(str(average).rstrip('0').rstrip('.'))
		elif a[i] == 'r':
			if x[i] not in lst:
				print('Wrong!')
			else:
				del lst[bisect.bisect_left(lst, x[i])]
				if len(lst) == 0:
					print('Wrong!')
					continue
				if len(lst) % 2 == 1:
					print(lst[len(lst) // 2])
				else:
					average = (lst[len(lst) // 2] + lst[len(lst) // 2 - 1]) / 2.0
					print(str(average).rstrip('0').rstrip('.'))
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import math

class MedianList:

	def __init__(self):
		self.m_list = []

	def add(self, value):
		ind = self.search(value)
		self.m_list.insert(ind, value)
		self.print_median()

	def remove(self, value):
		if not self.m_list == []:
			self.delete(value)
		else:
			print('Wrong!')

	def search(self, value):
		ind_min = 0
		ind_max = len(self.m_list) - 1
		while ind_max >= ind_min:
			mid = (ind_max + ind_min) // 2
			if self.m_list[mid] == value:
				return mid
			elif self.m_list[mid] < value:
				ind_min = mid + 1
			else:
				ind_max = mid - 1
		return ind_max + 1

	def delete(self, value):
		ind_min = 0
		ind_max = len(self.m_list) - 1
		while ind_max >= ind_min:
			mid = (ind_max + ind_min) // 2
			if self.m_list[mid] == value:
				del self.m_list[mid]
				self.print_median()
				return
			elif self.m_list[mid] < value:
				ind_min = mid + 1
			else:
				ind_max = mid - 1
		print('Wrong!')

	def print_median(self):
		median = self.median()
		if median == None:
			print('Wrong!')
			return
		if median == math.floor(median):
			median = math.floor(median)
		if median != None:
			print(median)

	def median(self):
		length = len(self.m_list)
		if length == 0:
			return None
		if length % 2 == 0:
			val = (self.m_list[length // 2] + self.m_list[length // 2 - 1]) / 2
		else:
			val = self.m_list[length // 2]
		return val

def median(a, x):
	ml = MedianList()
	for (command, value) in zip(a, x):
		if command == 'r':
			ml.remove(value)
		else:
			ml.add(value)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


def find_helper(lst, x, start=None, end=None):
	if start is None or end is None:
		start = 0
		end = len(lst) - 1
	if start >= end or lst[start] == x:
		return start
	if start > end:
		raise Exception('Bad (%d, %d)' % (start, end))
	ln = end - start + 1
	imid = start + ln // 2
	mid = lst[imid]
	if x < mid:
		return find_helper(lst, x, start, imid - 1)
	elif x == mid:
		return imid
	else:
		return find_helper(lst, x, imid + 1, end)

def find(lst, x):
	res = find_helper(lst, x)
	if res < len(lst) and x > lst[res]:
		res += 1
	return res

def add(lst, x):
	place = find(lst, x)
	lst.insert(place, x)
	assert lst[place] == x

def remove(lst, x):
	place = find(lst, x)
	if place < len(lst) and lst[place] == x:
		lst.pop(place)
		return True
	else:
		return False

def median(a, x):
	lst = []
	for (op, num) in zip(a, x):
		if op == 'a':
			add(lst, num)
		elif not remove(lst, num):
			print('Wrong!')
			continue
		if len(lst) == 0:
			print('Wrong!')
			continue
		even = len(lst) % 2 == 0
		if even:
			median = lst[len(lst) // 2] + lst[len(lst) // 2 - 1]
			if median % 2 == 0:
				median //= 2
			else:
				median //= 2
				median += 0.5
		else:
			median = lst[len(lst) // 2]
		print(median)

def main():
	N = int(input())
	s = []
	x = []
	for i in range(0, N):
		tmp = input().strip().split(' ')
		(a, b) = [xx for xx in tmp]
		s.append(a)
		x.append(int(b))
	median(s, x)
main()


from bisect import insort, bisect_left as bf
l = []

def m(l):
	ll = len(l)
	if ll == 0:
		return 'Wrong!'
	if ll % 2:
		return l[ll // 2]
	else:
		s = l[ll // 2] + l[ll // 2 - 1]
		if s % 2:
			return s / 2
		else:
			return s // 2
for i in range(int(input())):
	(a, b) = input().split()
	b = int(b)
	if a == 'a':
		insort(l, b)
		print(m(l))
	else:
		i = bf(l, b)
		if i == len(l) or l[i] != b:
			print('Wrong!')
		else:
			del l[i]
			print(m(l))


import bisect

def print_median(n_s):
	mid = len(n_s) // 2
	if len(n_s) % 2 == 0:
		out = (n_s[mid - 1] + n_s[mid]) / 2
	else:
		out = n_s[mid]
	if int(out) == out:
		print(int(out))
	else:
		print(out)
	return

def median(a, x):
	count = 0
	n_s = []
	for i in range(len(a)):
		ai = a[i]
		v = x[i]
		i_n = bisect.bisect_left(n_s, v)
		if ai == 'r':
			if not n_s:
				print('Wrong!')
			elif i_n == len(n_s) or n_s[i_n] != v:
				print('Wrong!')
			else:
				del n_s[i_n]
				if not n_s:
					print('Wrong!')
				else:
					print_median(n_s)
		else:
			bisect.insort_left(n_s, v)
			print_median(n_s)
	return
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


import bisect

def bs(L, t):
	mi = 0
	ma = len(L) - 1
	while True:
		if ma < mi:
			return 'Wrong!'
		m = (mi + ma) // 2
		if L[m] < t:
			mi = m + 1
		elif L[m] > t:
			ma = m - 1
		else:
			return m

def med(c, a, L):
	if c == 'r':
		try:
			i = bs(L, a)
			L.pop(i)
			print(median(L))
		except:
			print('Wrong!')
	else:
		bisect.insort_right(L, a)
		print(median(L))

def median(L):
	n = len(L)
	if n != 0:
		if n % 2 == 1:
			return L[n // 2]
		else:
			m1 = L[n // 2]
			m2 = L[n // 2 - 1]
			m = (m1 + m2) / 2
			if m % 1 == 0:
				return int(m)
			else:
				return m
	else:
		return 'Wrong!'
L = []
for i in range(int(input())):
	(c, a) = input().split()
	a = int(a)
	med(c, a, L)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


res = []
for testcase in range(int(input())):
	(op, n) = input().split()
	n = int(n)

	def find_idx(start, end, k):
		if start == end:
			return start
		else:
			median = int((start + end) / 2)
			return find_idx(median + 1, end, k) if k > res[median] else find_idx(start, median, k)
	idx = find_idx(0, len(res), n)
	if op == 'a':
		if res:
			res[idx:idx + 1] = [n, res[idx]] if idx < len(res) else [n]
		else:
			res = [n]
	else:
		try:
			if not res or res[idx] != n:
				raise Exception
			else:
				res[idx:idx + 1] = []
		except:
			print('Wrong!')
			continue
	len_res = len(res)
	med_res = int(len_res / 2)
	if len_res % 2:
		print(res[med_res])
	elif len_res:
		median = sum(res[med_res - 1:med_res + 1]) / 2
		print(int(median) if int(median) == median else median)
	else:
		print('Wrong!')


def insertNumber(array, number):
	if not array:
		array.append(number)
		return
	if len(array) == 1:
		if number > array[0]:
			array.append(number)
		else:
			array.insert(0, number)
		return
	si = 0
	ei = len(array) - 1
	binarySearchInsert(array, number, si, ei)

def binarySearchInsert(array, number, si, ei):
	if si == ei:
		if number > array[si]:
			array.insert(si + 1, number)
			return
		else:
			array.insert(si, number)
			return
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			binarySearchInsert(array, number, middle + 1, ei)
		elif number < array[middle]:
			binarySearchInsert(array, number, si, middle)
		else:
			array.insert(middle, number)
			return

def removeNumber(array, number):
	if not array:
		return False
	if len(array) == 1:
		if number == array[0]:
			array.pop()
			return True
		else:
			return False
	si = 0
	ei = len(array) - 1
	return binarySearchRemove(array, number, si, ei)

def binarySearchRemove(array, number, si, ei):
	if si == ei:
		if number == array[si]:
			array.pop(si)
			return True
		else:
			return False
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearchRemove(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearchRemove(array, number, si, middle)
		else:
			array.pop(middle)
			return True

def printMedian(nl):
	length = len(nl)
	if length == 0:
		print('Wrong!')
	else:
		if length % 2 == 1:
			index = length // 2
			median = nl[index]
		else:
			index1 = length // 2 - 1
			index2 = length // 2
			median = (nl[index1] + nl[index2]) / 2
		if int(median) == median:
			print(int(median))
		else:
			print(median)
n = int(input().strip())
nl = []
for op in range(n):
	operation = input().split(' ')
	if operation[0] == 'a':
		insertNumber(nl, int(operation[1]))
	elif not removeNumber(nl, int(operation[1])):
		print('Wrong!')
		continue
	printMedian(nl)


from random import random
from math import log, ceil
from collections import namedtuple
from functools import total_ordering
Node = namedtuple('Node', ['value', 'next', 'width'])

@total_ordering
class End(object):

	def __eq__(self, other):
		return False

	def __lt__(self, other):
		return False
NIL = Node(End(), [], [])

class IndexableSkiplist:

	def __init__(self, expected_size=100):
		self.size = 0
		self.maxlevels = int(1 + log(expected_size, 2))
		self.head = Node('HEAD', [NIL] * self.maxlevels, [1] * self.maxlevels)

	def __len__(self):
		return self.size

	def __getitem__(self, i):
		if i < 0 or i >= self.size:
			raise IndexError
		node = self.head
		i += 1
		for level in reversed(range(self.maxlevels)):
			while node.width[level] <= i:
				i -= node.width[level]
				node = node.next[level]
		return node.value

	def insert(self, value):
		chain = [None] * self.maxlevels
		steps_at_level = [0] * self.maxlevels
		node = self.head
		for level in reversed(range(self.maxlevels)):
			while node.next[level].value <= value:
				steps_at_level[level] += node.width[level]
				node = node.next[level]
			chain[level] = node
		d = min(self.maxlevels, 1 - int(log(random(), 2.0)))
		newnode = Node(value, [None] * d, [None] * d)
		steps = 0
		for level in range(d):
			prevnode = chain[level]
			newnode.next[level] = prevnode.next[level]
			prevnode.next[level] = newnode
			newnode.width[level] = prevnode.width[level] - steps
			prevnode.width[level] = steps + 1
			steps += steps_at_level[level]
		for level in range(d, self.maxlevels):
			chain[level].width[level] += 1
		self.size += 1

	def remove(self, value):
		chain = [None] * self.maxlevels
		node = self.head
		for level in reversed(range(self.maxlevels)):
			while node.next[level].value < value:
				node = node.next[level]
			chain[level] = node
		if value != chain[0].next[0].value:
			raise KeyError('Not Found')
		d = len(chain[0].next[0].next)
		for level in range(d):
			prevnode = chain[level]
			prevnode.width[level] += prevnode.next[level].width[level] - 1
			prevnode.next[level] = prevnode.next[level].next[level]
		for level in range(d, self.maxlevels):
			chain[level].width[level] -= 1
		self.size -= 1

	def __iter__(self):
		node = self.head.next[0]
		while node is not NIL:
			yield node.value
			node = node.next[0]

def get_median(sk):
	if len(sk) == 0:
		return 'Wrong!'
	median_index = len(sk) // 2
	if len(sk) % 2 == 1:
		return sk[median_index]
	total = sk[median_index - 1] + sk[median_index]
	if total % 2 == 0:
		return total // 2
	return total // 2 + 0.5

def get_commands():
	num_of_commands = int(input())
	commands = []
	for _ in range(num_of_commands):
		(action, value_str) = input().strip().split(' ')
		value = int(value_str)
		commands.append((action, value))
	return commands

def run_commands(commands, output=True):
	sk = IndexableSkiplist(10000)
	for (action, value) in commands:
		if action == 'a':
			sk.insert(value)
			print(get_median(sk))
		if action == 'r':
			try:
				result = sk.remove(value)
			except KeyError:
				print('Wrong!')
			else:
				print(get_median(sk))
commands = get_commands()
run_commands(commands)


import math
import bisect

def slow_median(values, size):
	if size % 2 == 0:
		mid = math.floor(size / 2)
		return ((values[mid - 1] + values[mid]) / 2, float)
	else:
		return (values[math.floor(size / 2)], int)

def median(op, value, values):
	if op == 'a':
		bisect.insort(values, value)
	elif op == 'r':
		pos = bisect.bisect(values, value)
		if pos > 0 and values[pos - 1] == value:
			values.pop(pos - 1)
		else:
			print('Wrong!')
			return values
	size = len(values)
	if size > 3:
		(m, t) = slow_median(values, size)
	elif size == 0:
		print('Wrong!')
		return values
	elif size == 1:
		print(values[0])
		return values
	elif size == 2:
		(m, t) = ((values[0] + values[1]) / 2, float)
	elif size == 3:
		print(values[1])
		return values
	if t is int:
		print(m)
	elif m >= 0 and math.ceil(m) == int(m):
		print(int(m))
	elif m < 0 and math.floor(m) == int(m):
		print(int(m))
	else:
		print(m)
	return values
N = int(input())
values = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	values = median(a, int(b), values)


def insertNumber(array, number):
	if not array:
		array.append(number)
		return
	if len(array) == 1:
		if number > array[0]:
			array.append(number)
		else:
			array.insert(0, number)
		return
	si = 0
	ei = len(array) - 1
	binarySearchInsert(array, number, si, ei)

def binarySearchInsert(array, number, si, ei):
	if si == ei:
		if number > array[si]:
			array.insert(si + 1, number)
			return
		else:
			array.insert(si, number)
			return
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			binarySearchInsert(array, number, middle + 1, ei)
		elif number < array[middle]:
			binarySearchInsert(array, number, si, middle)
		else:
			array.insert(middle, number)
			return

def removeNumber(array, number):
	if not array:
		return False
	if len(array) == 1:
		if number == array[0]:
			array.pop()
			return True
		else:
			return False
	si = 0
	ei = len(array) - 1
	return binarySearchRemove(array, number, si, ei)

def binarySearchRemove(array, number, si, ei):
	if si == ei:
		if number == array[si]:
			array.pop(si)
			return True
		else:
			return False
	else:
		middle = (ei - si) // 2 + si
		if number > array[middle]:
			return binarySearchRemove(array, number, middle + 1, ei)
		elif number < array[middle]:
			return binarySearchRemove(array, number, si, middle)
		else:
			array.pop(middle)
			return True

def printMedian(nl):
	length = len(nl)
	if length == 0:
		print('Wrong!')
	else:
		if length % 2 == 1:
			index = length // 2
			median = nl[index]
		else:
			index1 = length // 2 - 1
			index2 = length // 2
			median = (nl[index1] + nl[index2]) / 2
		if int(median) == median:
			print(int(median))
		else:
			print(median)
n = int(input().strip())
nl = []
for op in range(n):
	operation = input().split(' ')
	if operation[0] == 'a':
		insertNumber(nl, int(operation[1]))
	elif not removeNumber(nl, int(operation[1])):
		print('Wrong!')
		continue
	printMedian(nl)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


import bisect, sys
n = int(sys.stdin.readline())
a = []
len_a = 0
for i in range(n):
	(action, x) = sys.stdin.readline().split()
	idx = bisect.bisect_left(a, int(x))
	if action == 'r':
		if idx >= len_a or a[idx] != int(x):
			print('Wrong!')
			continue
		else:
			del a[idx]
			len_a -= 1
	elif action == 'a':
		a.insert(idx, int(x))
		len_a += 1
	else:
		print('Wrong!')
		continue
	mid = len_a // 2
	if len_a == 0:
		print('Wrong!')
	elif len_a % 2:
		print(a[mid])
	else:
		x = a[mid - 1] + a[mid]
		print(x / 2 if x % 2 else x // 2)


import bisect

def median(a, x):
	l = []
	for (op, num) in zip(a, x):
		if op == 'r':
			try:
				l.remove(num)
			except ValueError:
				print('Wrong!')
				continue
		elif op == 'a':
			bisect.insort(l, num)
		if len(l) % 2 == 1:
			print('{0:.1f}'.format(float(l[len(l) // 2])).replace('.0', ''))
		elif len(l) > 0:
			print('{0:.1f}'.format(float((l[len(l) // 2 - 1] + l[len(l) // 2]) / 2)).replace('.0', ''))
		else:
			print('Wrong!')
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import bisect as bi
from math import floor

def index(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	raise ValueError

def print_median(median_list):
	median_idx = floor((len(median_list) - 1) / 2)
	median_integer = median_list[median_idx]
	if len(median_list) % 2 == 0:
		print(str((median_integer + median_list[median_idx + 1]) / 2).rstrip('0').rstrip('.'))
	else:
		print(median_integer)

def median(operations, integers):
	median_list = []
	for (operation, integer) in zip(operations, integers):
		if operation == 'a':
			bi.insort(median_list, integer)
			print_median(median_list)
		elif operation == 'r':
			try:
				idx = index(median_list, integer)
				median_list.pop(idx)
				print_median(median_list)
			except:
				print('Wrong!')
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import bisect

class Median:

	def __init__(self):
		self.list = []

	def add(self, x):
		bisect.insort(self.list, x)

	def get_median(self):
		if len(self.list) == 0:
			return None
		if len(self.list) % 2 == 0:
			res = (self.list[len(self.list) // 2 - 1] + self.list[len(self.list) // 2]) / 2
			return int(res) if res % 1 == 0 else res
		return self.list[len(self.list) // 2]

	def remove(self, x):
		i = bisect.bisect_left(self.list, x)
		if i != len(self.list) and self.list[i] == x:
			del self.list[i]
			return True
		return False

def median(a, x):
	med = Median()
	for i in range(len(a)):
		if a[i] == 'a':
			med.add(x[i])
			print(str(med.get_median()))
		elif med.remove(x[i]):
			res = med.get_median()
			print('Wrong!' if res == None else str(res))
		else:
			print('Wrong!')
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import fileinput
import heapq
import collections

class Values(object):

	def __init__(self):
		self._values = collections.Counter()
		self._max_heap = []
		self._max_heap_count = 0
		self._max_heap_bl = collections.Counter()
		self._min_heap = []
		self._min_heap_count = 0
		self._min_heap_bl = collections.Counter()

	def __len__(self):
		return self._max_heap_count + self._min_heap_count

	def __contains__(self, x):
		return self._values[x] > 0

	def _update_heaps(self):
		self._cleanup_heaps()
		self._balance_heaps()
		self._cleanup_heaps()

	def _balance_heaps(self):
		if self._max_heap_count - self._min_heap_count > 1:
			x = -heapq.heappop(self._max_heap)
			self._max_heap_count -= 1
			heapq.heappush(self._min_heap, x)
			self._min_heap_count += 1
		if self._min_heap_count - self._max_heap_count > 1:
			x = heapq.heappop(self._min_heap)
			self._min_heap_count -= 1
			heapq.heappush(self._max_heap, -x)
			self._max_heap_count += 1

	def _cleanup_heaps(self):
		self._cleanup_heap(self._max_heap, self._max_heap_bl)
		self._cleanup_heap(self._min_heap, self._min_heap_bl)

	def _cleanup_heap(self, heap, heap_bl):
		while heap and heap_bl[heap[0]] > 0:
			x = heapq.heappop(heap)
			heap_bl[x] -= 1
			if heap_bl[x] == 0:
				del heap_bl[x]

	def add(self, x):
		self._values[x] += 1
		if not self._max_heap or x <= -self._max_heap[0]:
			heapq.heappush(self._max_heap, -x)
			self._max_heap_count += 1
		else:
			heapq.heappush(self._min_heap, x)
			self._min_heap_count += 1
		self._update_heaps()

	def remove(self, x):
		self._values[x] -= 1
		if self._values[x] == 0:
			del self._values[x]
		if x <= -self._max_heap[0]:
			self._max_heap_bl[-x] += 1
			self._max_heap_count -= 1
		else:
			self._min_heap_bl[x] += 1
			self._min_heap_count -= 1
		self._update_heaps()

	def get_median(self):
		if self._max_heap_count > self._min_heap_count:
			return -self._max_heap[0]
		elif self._min_heap_count > self._max_heap_count:
			return self._min_heap[0]
		else:
			x = -self._max_heap[0]
			y = self._min_heap[0]
			return (x + y) / 2

def format_median(median):
	return ('%f' % median).rstrip('0').rstrip('.')
values = Values()
with fileinput.input() as fi:
	N = int(fi.readline())
	for n in range(N):
		(op, x) = fi.readline().strip().split()
		x = int(x)
		if op == 'a':
			values.add(x)
			print(format_median(values.get_median()))
		elif op == 'r':
			if x in values:
				values.remove(x)
				if values:
					print(format_median(values.get_median()))
				else:
					print('Wrong!')
			else:
				print('Wrong!')


from array import array
from bisect import bisect_left, insort_left

def print_median(a):
	n = len(a)
	if not n:
		print('Wrong!')
		return
	(m, r) = divmod(n - 1, 2)
	if r:
		aux = a[m] + a[m + 1]
		if aux & 1:
			print(aux / 2)
		else:
			print(aux // 2)
	else:
		print(a[m])
n_ops = int(input())
data = array('l')
for _ in range(n_ops):
	(c, x) = input().split()
	x = int(x)
	if c == 'a':
		insort_left(data, x)
		print_median(data)
	else:
		i = bisect_left(data, x)
		if i < len(data) and data[i] == x:
			data.pop(i)
			print_median(data)
		else:
			print('Wrong!')


from bisect import insort
from collections import defaultdict
import sys

def main():
	f = sys.stdin
	bag = defaultdict(int)
	numbers = []
	l = 0
	n = int(f.readline())
	for i in range(n):
		(opt, num) = [i for i in f.readline().split()]
		num = int(num)
		if opt == 'a':
			l += 1
			insort(numbers, num)
			bag[num] += 1
			if l % 2:
				print(numbers[l // 2])
			else:
				output = (numbers[l // 2] + numbers[l // 2 - 1]) / 2.0
				output = int(output) if output.is_integer() else output
				print(output)
		else:
			if num in bag:
				l -= 1
				bag[num] -= 1
				numbers.remove(num)
				if bag[num] == 0:
					del bag[num]
			else:
				print('Wrong!')
				continue
			if l % 2 and l > 0:
				print(numbers[l // 2])
			elif l > 0:
				output = (numbers[l // 2] + numbers[l // 2 - 1]) / 2.0
				output = int(output) if output.is_integer() else output
				print(output)
			else:
				print('Wrong!')
main()


def median(o, x, values):
	if o == 'a':
		(idx, found) = binary_search(x, values)
		values.insert(idx, x)
	elif o == 'r':
		(idx, found) = binary_search(x, values)
		if not found:
			print('Wrong!')
			return
		values.pop(idx)
	length = len(values)
	if length > 0:
		mid = (length - 1) // 2
		if length % 2 == 1:
			median = values[mid]
		else:
			median = (values[mid] + values[mid + 1]) / 2
		print('{0:f}'.format(median).rstrip('0').rstrip('.'))
	else:
		print('Wrong!')

def binary_search(v, values):
	if not values:
		return (0, False)
	(start, end) = (0, len(values) - 1)
	while start + 1 < end:
		mid = (start + end) // 2
		if v == values[mid]:
			end = mid
		elif v > values[mid]:
			start = mid
		elif v < values[mid]:
			end = mid
	if v < values[start]:
		return (start, False)
	elif v == values[start]:
		return (start, True)
	elif v < values[end]:
		return (end, False)
	elif v == values[end]:
		return (end, True)
	else:
		return (end + 1, False)
N = int(input().strip())
values = []
for i in range(0, N):
	(a, b) = input().strip().split(' ')
	median(a, int(b), values)


import bisect
theList = []
seenValues = {}

def find_index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	raise ValueError

def printMedian():
	if len(theList) == 0:
		print('Wrong!')
		return
	if len(theList) % 2 != 0:
		middleElement = int(len(theList) / 2)
		print(str(theList[middleElement]))
	else:
		mid1Index = int(len(theList) / 2)
		mid2Index = mid1Index - 1
		median = round((theList[mid1Index] + theList[mid2Index]) / 2, 1)
		print('{0:.32g}'.format(float(median)))

def addOperation(inputVal):
	bisect.insort(theList, inputVal)
	printMedian()

def removeOperation(inputVal):
	if len(theList) == 0:
		print('Wrong!')
		return
	try:
		del theList[find_index(theList, inputVal)]
	except:
		print('Wrong!')
		return
	printMedian()

def median(a, x):
	if len(a) != len(x):
		print('Error: input array lengths unequal')
		return
	for i in range(len(a)):
		if a[i] == 'a':
			addOperation(x[i])
		elif a[i] == 'r':
			removeOperation(x[i])
		else:
			print('Error: given unknown command: ' + a[i])
			return
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import heapq
from collections import defaultdict

def swim_min(index, pq, qp):
	while index > 1 and pq[index] < pq[index // 2]:
		(pq[index], pq[index // 2]) = (pq[index // 2], pq[index])
		qp[pq[index]][qp[pq[index]].index(index // 2)] = index
		qp[pq[index // 2]][qp[pq[index // 2]].index(index)] = index // 2
		index //= 2

def swim_max(index, pq, qp):
	while index > 1 and pq[index] > pq[index // 2]:
		(pq[index], pq[index // 2]) = (pq[index // 2], pq[index])
		qp[pq[index]][qp[pq[index]].index(index // 2)] = index
		qp[pq[index // 2]][qp[pq[index // 2]].index(index)] = index // 2
		index //= 2

def sink_min(index, pq, qp, size):
	while 2 * index <= size:
		j = 2 * index
		if j < size and pq[j] > pq[j + 1]:
			j += 1
		if pq[index] <= pq[j]:
			break
		(pq[index], pq[j]) = (pq[j], pq[index])
		qp[pq[index]][qp[pq[index]].index(j)] = index
		qp[pq[j]][qp[pq[j]].index(index)] = j
		index = j

def sink_max(index, pq, qp, size):
	while 2 * index <= size:
		j = 2 * index
		if j < size and pq[j] < pq[j + 1]:
			j += 1
		if pq[index] >= pq[j]:
			break
		(pq[index], pq[j]) = (pq[j], pq[index])
		qp[pq[index]][qp[pq[index]].index(j)] = index
		qp[pq[j]][qp[pq[j]].index(index)] = j
		index = j

def insert_min(value, pq, qp, size):
	size += 1
	pq[size] = value
	qp[value].append(size)
	swim_min(size, pq, qp)
	return size

def insert_max(value, pq, qp, size):
	size += 1
	pq[size] = value
	qp[value].append(size)
	swim_max(size, pq, qp)
	return size

def delete_min(index, pq, qp, size):
	qp[pq[index]].remove(index)
	if not qp[pq[index]]:
		qp.pop(pq[index])
	if index < size:
		pq[index] = pq[size]
		qp[pq[index]][qp[pq[index]].index(size)] = index
		swim_min(index, pq, qp)
		sink_min(index, pq, qp, size)
	return size - 1

def delete_max(index, pq, qp, size):
	qp[pq[index]].remove(index)
	if not qp[pq[index]]:
		qp.pop(pq[index])
	if index < size:
		pq[index] = pq[size]
		qp[pq[index]][qp[pq[index]].index(size)] = index
		swim_max(index, pq, qp)
		sink_max(index, pq, qp, size)
	return size - 1

def balance(heapmax_size, heapmax, heapmax_dict, heapmin_size, heapmin, heapmin_dict):
	if abs(heapmax_size - heapmin_size) > 1:
		if heapmax_size > heapmin_size:
			maxx = heapmax[1]
			heapmax_size = delete_max(1, heapmax, heapmax_dict, heapmax_size)
			heapmin_size = insert_min(maxx, heapmin, heapmin_dict, heapmin_size)
		else:
			minn = heapmin[1]
			heapmin_size = delete_min(1, heapmin, heapmin_dict, heapmin_size)
			heapmax_size = insert_max(minn, heapmax, heapmax_dict, heapmax_size)
	return (heapmax_size, heapmin_size)

def median(a, x):
	heapmax_size = heapmin_size = median = 0
	heapmax_dict = defaultdict(list)
	heapmin_dict = defaultdict(list)
	heapmax = [0] * 10 ** 6
	heapmin = [0] * 10 ** 6
	for (query, a) in zip(a, x):
		if query == 'a':
			if a > median:
				heapmin_size = insert_min(a, heapmin, heapmin_dict, heapmin_size)
			else:
				heapmax_size = insert_max(a, heapmax, heapmax_dict, heapmax_size)
		else:
			if a not in heapmin_dict and a not in heapmax_dict:
				print('Wrong!')
				continue
			if a in heapmin_dict:
				index = heapmin_dict[a][-1]
				heapmin_size = delete_min(index, heapmin, heapmin_dict, heapmin_size)
			else:
				index = heapmax_dict[a][-1]
				heapmax_size = delete_max(index, heapmax, heapmax_dict, heapmax_size)
		(heapmax_size, heapmin_size) = balance(heapmax_size, heapmax, heapmax_dict, heapmin_size, heapmin, heapmin_dict)
		if heapmax_size == heapmin_size == 0:
			print('Wrong!')
		else:
			if heapmax_size == heapmin_size:
				median = (heapmin[1] + heapmax[1]) / 2
			elif heapmax_size > heapmin_size:
				median = heapmax[1]
			else:
				median = heapmin[1]
			if median == int(median):
				median = int(median)
			print(median)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from random import random

class TreapNode(object):

	def __init__(self, val):
		self.val = val
		self.priority = random()
		self.size = 1
		self.left = None
		self.right = None

	def updatesize(self):
		self.size = (0 if self.left is None else self.left.size) + 1 + (0 if self.right is None else self.right.size)

class ImplicitTreap(object):

	def __init__(self):

		def list2treap(lst):
			if lst is None or len(lst) == 0:
				return None
			if len(lst) == 1:
				return TreapNode(lst[0])
			mid = len(lst) // 2
			return self.merge(list2treap(lst[:mid]), list2treap(lst[mid:]))
		self.root = None

	def move2front(self, i, j):
		i -= 1
		l = self.splitbeforeith(i)
		m = self.splitbeforeith(j - i)
		self.merge2front(l)
		self.merge2front(m)

	def move2rear(self, i, j):
		i -= 1
		l = self.splitbeforeith(i)
		m = self.splitbeforeith(j - i)
		self.merge2front(l)
		self.merge2rear(m)

	def median(self):

		def medeven(root, i):
			if root.left is not None:
				if root.left.size == i:
					return (self.getfirst(root.right).val + root.val) / 2.0
				elif root.left.size == i + 1:
					return (self.getlast(root.left).val + root.val) / 2.0
				elif root.left.size > i + 1:
					return medeven(root.left, i)
				else:
					return medeven(root.right, i - root.left.size - 1)
			elif root.right is not None:
				if i < 1:
					return (self.getfirst(root.right).val + root.val) / 2.0
				else:
					return medeven(root.right, i - 1)
			else:
				print(i)
				print(self)
				raise Error

		def medodd(root, i):
			if root.left is not None:
				if root.left.size == i:
					return root.val
				elif root.left.size > i:
					return medodd(root.left, i)
				else:
					return medodd(root.right, i - root.left.size - 1)
			elif root.right is not None:
				if i == 0:
					return root.val
				else:
					return medodd(root.right, i - 1)
			else:
				return root.val
		if self.root is None:
			return None
		if self.root.size % 2 == 0:
			return medeven(self.root, (self.root.size - 1) // 2)
		else:
			return medodd(self.root, (self.root.size - 1) // 2)

	def add(self, val):
		l = self.splitbeforeval(val)
		self.merge2front(TreapNode(val))
		self.merge2front(l)
		return True

	def remove(self, val):
		if self.root is None:
			return False
		l = self.splitbeforeval(val)
		rem = self.splitbeforeval(val + 1)
		found = False
		if rem is not None:
			found = True
			if rem.size == 1:
				rem = None
			else:
				curr = rem
				while True:
					curr.size -= 1
					if curr.left is not None and curr.left.size == 1:
						curr.left = None
						break
					if curr.right is not None and curr.right.size == 1:
						curr.right = None
						break
					if curr.left is not None and (curr.right is None or curr.right.size >= curr.left.size):
						curr = curr.left
						continue
					curr = curr.right
				self.merge2front(rem)
		self.merge2front(l)
		return found

	def splitbeforeval(self, val):
		if self.root is None:
			return None

		def split(root, val):
			if root is None:
				return (None, None)
			if root.val < val:
				((root.right, r), l) = (split(root.right, val), root)
			else:
				((l, root.left), r) = (split(root.left, val), root)
			root.updatesize()
			return (l, r)
		(l, r) = split(self.root, val)
		self.root = r
		return l

	def merge(self, l, r):
		if l is None or r is None:
			newroot = l if l is not None else r
		elif l.priority > r.priority:
			(l.right, newroot) = (self.merge(l.right, r), l)
		else:
			(r.left, newroot) = (self.merge(l, r.left), r)
		if newroot is not None:
			newroot.updatesize()
		return newroot

	def merge2front(self, other):
		self.root = self.merge(other, self.root)

	def merge2rear(self, other):
		self.root = self.merge(self.root, other)

	def getlast(self, root=None):
		if root is not None and root.right is not None:
			return self.getlast(root.right)
		return root

	def getfirst(self, root=None):
		if root is not None and root.left is not None:
			return self.getfirst(root.left)
		return root

	def lastminusfirst(self):
		if self.root is None:
			return 0
		return abs(self.getlast(self.root).val - self.getfirst(self.root).val)

	def inorder(self):

		def pio(root, ret):
			if root is None:
				return ret
			ret = pio(root.left, ret)
			ret.append(str(root.val))
			ret = pio(root.right, ret)
			return ret
		return ' '.join(pio(self.root, []))

	def __str__(self):
		return '\n'.join([str(self.lastminusfirst()), self.inorder()])

class Solution(object):

	def add(self, val):
		return self.st.add(val)

	def remove(self, val):
		return self.st.remove(val)

	def setst(self, st):
		self.st = st
		self.qs = {'a': self.add, 'r': self.remove}

	def query(self, q, v):
		return self.qs[q](int(v))

	def median(self):
		ret = self.st.median()
		if ret is None:
			return 'Wrong!'
		elif ret == int(ret):
			return int(ret)
		return ret

	def run(self):
		n = int(input())
		self.setst(ImplicitTreap())
		for _ in range(n):
			if not self.query(*input().split()):
				print('Wrong!')
			else:
				print(self.median())
Solution().run()


class Node:

	def __init__(self, v):
		self.value = v
		self.height = 0
		self.size = 1
		self.left = None
		self.right = None

	def branching_factor(self):
		lh = 0 if self.left == None else self.left.height + 1
		rh = 0 if self.right == None else self.right.height + 1
		return lh - rh

	def update(self):
		self.__set_height()
		self.__set_size()

	def __set_height(self):
		lh = 0 if self.left == None else self.left.height + 1
		rh = 0 if self.right == None else self.right.height + 1
		self.height = max(lh, rh)

	def __set_size(self):
		ls = 0 if self.left == None else self.left.size
		rs = 0 if self.right == None else self.right.size
		self.size = ls + rs + 1

class AVLTree:

	def __init__(self):
		self.__root = None

	def insert(self, val):
		self.__root = self.__insert(self.__root, val)

	def __insert(self, root, val):
		if root == None:
			return Node(val)
		if val <= root.value:
			root.left = self.__insert(root.left, val)
		else:
			root.right = self.__insert(root.right, val)
		return self.__balance(root)

	def remove(self, val):
		size_before = 0 if self.__root == None else self.__root.size
		self.__root = self.__remove(self.__root, val)
		size_after = 0 if self.__root == None else self.__root.size
		if size_before == size_after:
			return False
		return True

	def __remove(self, root, val):
		if root == None:
			return root
		if val < root.value:
			root.left = self.__remove(root.left, val)
		elif val > root.value:
			root.right = self.__remove(root.right, val)
		elif root.left == None and root.right == None:
			return None
		elif (root.left == None) != (root.right == None):
			return root.left if root.right == None else root.right
		else:
			path = []
			successor = root.right
			while successor.left != None:
				path.append(successor)
				successor = successor.left
			if path:
				path[-1].left = successor.right
			else:
				root.right = successor.right
			successor.left = root.left
			successor.right = root.right
			root = successor
			while path:
				cur = self.__balance(path.pop())
				try:
					path[-1].left = cur
				except IndexError:
					root.right = cur
		return self.__balance(root)

	def __balance(self, root):
		BF = root.branching_factor()
		rotated = False
		if BF == 2:
			if root.left.branching_factor() == -1:
				temp = root.left.right
				root.left.right = temp.left
				temp.left = root.left
				root.left = temp
			temp = root.left
			root.left = temp.right
			temp.right = root
			root = temp
			rotated = True
		elif BF == -2:
			if root.right.branching_factor() == 1:
				temp = root.right.left
				root.right.left = temp.right
				temp.right = root.right
				root.right = temp
			temp = root.right
			root.right = temp.left
			temp.left = root
			root = temp
			rotated = True
		if rotated:
			if root.left:
				root.left.update()
			if root.right:
				root.right.update()
		root.update()
		return root

	def median(self):
		if self.__root == None:
			return 'Wrong!'
		size = self.__root.size
		med = None
		if size % 2 == 0:
			a = self.__get(size / 2 - 1, self.__root)
			b = self.__get(size / 2, self.__root)
			med = (a.value + b.value) / 2
		else:
			med = self.__get(size // 2, self.__root).value
		return med

	def __get(self, idx, root, add=0):
		if root == None:
			return None
		ls = 0 if root.left == None else root.left.size
		pos = ls + add
		if pos < idx:
			return self.__get(idx, root.right, pos + 1)
		elif pos > idx:
			return self.__get(idx, root.left, add)
		else:
			return root

	def bft(self):
		queue = [self.__root]
		while queue:
			cur = queue.pop(0)
			if cur:
				print(cur.value, end=' ')
				queue.extend([cur.left, cur.right])

def formatted(f):
	return format(f, '.8f').rstrip('0').rstrip('.')

def median(a, x):
	tree = AVLTree()
	for (act, v) in zip(a, x):
		if act == 'a':
			tree.insert(v)
		elif act == 'r':
			if not tree.remove(v):
				print('Wrong!')
				continue
		med = tree.median()
		if not isinstance(med, str):
			med = formatted(med)
		print(med)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from heapq import heappush as push, heappop as pop
(M, m, R, r, d, L, l) = ([], [], {}, {}, {}, 0, 0)
for _ in range(int(input())):
	(c, x) = input().split()
	x = int(x)
	try:
		if c == 'a':
			if not (L or l) or (L and x <= -M[0]) or (not l):
				L += 1
				push(M, -x)
			else:
				l += 1
				push(m, x)
			d[x] = 1 + d.get(x, 0)
		elif d.get(x, 0):
			d[x] -= 1
			if L and x <= -M[0]:
				R[x] = 1 + R.get(x, 0)
				L -= 1
			else:
				r[x] = 1 + r.get(x, 0)
				l -= 1
		else:
			raise KeyError
		if not (L or l):
			raise KeyError
		while L - l > 1:
			x = -pop(M)
			if R.get(x, 0):
				R[x] -= 1
			else:
				L -= 1
				l += 1
				push(m, x)
		while l - L > 1:
			x = pop(m)
			if r.get(x, 0):
				r[x] -= 1
			else:
				L += 1
				l -= 1
				push(M, -x)
		while M and R.get(-M[0], 0):
			R[-pop(M)] -= 1
		while m and r.get(m[0], 0):
			r[pop(m)] -= 1
		if L == l:
			x = m[0] - M[0]
			print(x / 2 if x & 1 else x // 2)
		else:
			print(-M[0] if L > l else m[0])
	except KeyError:
		print('Wrong!')


import bisect

def Median(arr):
	if not len(arr):
		print('Wrong!')
	elif len(arr) % 2:
		print(arr[len(arr) // 2])
	else:
		result = arr[len(arr) // 2 - 1] + arr[len(arr) // 2]
		print(result / 2 if result % 2 else result // 2)
arr = []
for _ in range(int(input())):
	(command, val) = input().split()
	if command == 'a':
		bisect.insort(arr, int(val))
		Median(arr)
	else:
		pos = bisect.bisect_left(arr, int(val))
		if len(arr) and pos != len(arr) and (arr[pos] == int(val)):
			del arr[pos]
			Median(arr)
		else:
			print('Wrong!')


import bisect
N = int(input())
s = []
x = []
length = 0
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	b = int(b)
	if a == 'a':
		bisect.insort(x, b)
		length += 1
	else:
		index = bisect.bisect_left(x, b)
		if index != length and x[index] == b:
			del x[index]
			length -= 1
		else:
			print('Wrong!')
			continue
	if length <= 0:
		print('Wrong!')
		continue
	(nforme, nfm) = divmod(length, 2)
	nforme -= 1
	if nfm > 0:
		nforme += 1
		print(x[nforme])
	else:
		nfm = nforme + 1
		median = x[nforme] + x[nfm]
		median /= 2
		if round(median) == median:
			median = round(median)
		print(median)


from bisect import bisect_left

class Median:

	def __init__(self):
		self.values = []

	def add(self, x):
		i = bisect_left(self.values, x)
		self.values.insert(i, x)
		return self.getMedian()

	def remove(self, x):
		i = bisect_left(self.values, x)
		if i >= len(self.values) or self.values[i] != x:
			return None
		y = self.values.pop(i)
		return self.getMedian()

	def getMedian(self):
		l = len(self.values)
		if l == 0:
			return None
		if l & 1 == 1:
			return self.values[l // 2]
		else:
			return (self.values[l // 2] + self.values[l // 2 - 1]) / 2
median = Median()
for _ in range(int(input())):
	(a, x) = input().split()
	x = int(x)
	if a == 'a':
		m = median.add(x)
	else:
		m = median.remove(x)
	if m == None:
		print('Wrong!')
	elif int(m) == m:
		print(int(m))
	else:
		print('%0.1f' % m)


import sys
import random
from functools import total_ordering
import decimal
seed = random.randint(0, sys.maxsize)
myRand = random.Random(seed)

def remove_exponent(d):
	d = decimal.Decimal(d)
	return d.quantize(decimal.Decimal(1)) if d == d.to_integral() else d.normalize()

class EmptyTreeError(Exception):

	def __init__(self):
		self.error = 'Empty tree'

class node(object):

	def __init__(self, val, prty, prnt=None, lchild=None, rchild=None):
		self.prnt = prnt
		self.lchild = lchild
		self.rchild = rchild
		self.val = val
		self.prty = prty
		self.size = 1

	def __str__(self, *args, **kwargs):
		return str((self.val, self.prty, self.size, (self.prnt.val, self.prnt.prty) if self.prnt else None))

	def recalc_size(self):
		self.size = (self.lchild.size if self.lchild else 0) + (self.rchild.size if self.rchild else 0) + 1

	def find_root(self):
		p = self
		while p.prnt != None:
			p = p.prnt
		return p

	def ppprint(self):
		return self.pprint([], True, [])

	def pprint(self, pref, isTail, sb):
		if self.rchild:
			t = pref + list('│   ' if isTail else '    ')
			self.rchild.pprint(t, False, sb)
		t = pref + list('└── ' if isTail else '┌── ') + list(str(self))
		sb.append(t)
		if self.lchild:
			t = pref + list('    ' if isTail else '│   ')
			self.lchild.pprint(t, True, sb)
		return sb

@total_ordering
class End(object):

	def __lt__(self, other):
		return False
BOT = End()

def rotate_left(p, r):
	p.rchild = r.lchild
	if p.rchild != None:
		p.rchild.prnt = p
	r.lchild = p
	if p.prnt:
		if p == p.prnt.lchild:
			p.prnt.lchild = r
		else:
			p.prnt.rchild = r
	r.prnt = p.prnt
	p.prnt = r
	p.recalc_size()
	r.recalc_size()

def rotate_right(p, q):
	p.lchild = q.rchild
	if p.lchild != None:
		p.lchild.prnt = p
	q.rchild = p
	if p.prnt:
		if p.prnt.lchild and p == p.prnt.lchild:
			p.prnt.lchild = q
		else:
			p.prnt.rchild = q
	q.prnt = p.prnt
	p.prnt = q
	p.recalc_size()
	q.recalc_size()

def bubble_up(p):
	while p.prnt and p.prty < p.prnt.prty:
		if p == p.prnt.lchild:
			rotate_right(p.prnt, p)
		else:
			rotate_left(p.prnt, p)

def bubble_down(p):
	while p.lchild and p.prty > p.lchild.prty or (p.rchild and p.prty > p.rchild.prty):
		if p.lchild != None and (p.rchild == None or p.lchild.prty < p.rchild.prty):
			rotate_right(p, p.lchild)
		elif p.rchild != None and (p.lchild == None or p.rchild.prty < p.lchild.prty):
			rotate_left(p, p.rchild)

def insert(root, key):
	p = root
	while p.lchild and key <= p.val or (p.rchild and key > p.val):
		if p.lchild and key <= p.val:
			p = p.lchild
		else:
			p = p.rchild
	if key <= p.val:
		nod = node(key, myRand.uniform(0, 1), p)
		p.lchild = nod
	else:
		nod = node(key, myRand.uniform(0, 1), p)
		p.rchild = nod
	p = nod
	while p != None:
		p.recalc_size()
		p = p.prnt
	bubble_up(nod)

def delete(p):
	p.prty = BOT
	bubble_down(p)
	if p.prnt:
		if p.prnt.lchild and p == p.prnt.lchild:
			p.prnt.lchild = None
		else:
			p.prnt.rchild = None
		while p != None:
			p.recalc_size()
			p = p.prnt
	else:
		raise EmptyTreeError

def select(p, i):
	try:
		rank = (p.lchild.size if p.lchild else 0) + 1
	except:
		print(p, i)
	if i == rank:
		return p.val
	elif i < rank:
		return select(p.lchild, i)
	else:
		return select(p.rchild, i - rank)

def remove(root, key):
	p = root
	while p.lchild and key < p.val or (p.rchild and key > p.val):
		if p.lchild and key < p.val:
			p = p.lchild
		else:
			p = p.rchild
	if p.val == key:
		delete(p)
	else:
		raise KeyError

def find_succ(p):
	if p.rchild:
		p = p.rchild
		while p.lchild:
			p = p.lchild
		return p
	else:
		while p.prnt.prnt and p.prnt != p.prnt.prnt.lchild:
			p = p.prnt
		if p.prnt.prnt == None:
			return None
		else:
			return p.prnt.prnt
n = int(input())
tree = None
size_tree = 0
for _ in range(n):
	(q, i) = input().strip().split()
	if q == 'a':
		size_tree += 1
		if tree == None:
			tree = node(int(i), myRand.uniform(0, 1))
		else:
			insert(tree.find_root(), int(i))
		if size_tree % 2 == 1:
			print(remove_exponent(select(tree.find_root(), size_tree // 2 + 1)))
		else:
			print(remove_exponent((select(tree.find_root(), size_tree // 2) + select(tree.find_root(), size_tree // 2 + 1)) / 2))
		tree = tree.find_root()
	elif tree == None:
		print('Wrong!')
	else:
		try:
			remove(tree.find_root(), int(i))
			size_tree -= 1
		except EmptyTreeError:
			tree = None
			size_tree = 0
			print('Wrong!')
			continue
		except KeyError:
			print('Wrong!')
			continue
		if size_tree % 2 == 1:
			print(remove_exponent(select(tree.find_root(), size_tree // 2 + 1)))
		else:
			print(remove_exponent((select(tree.find_root(), size_tree // 2) + select(tree.find_root(), size_tree // 2 + 1)) / 2))
		tree = tree.find_root()


import heapq
import sys
from collections import Counter

class DeletableHeap:

	def __init__(self):
		self.len = 0
		self.counts = Counter()
		self.heap = []

	def head(self):
		while self.heap[0] not in self.counts:
			heapq.heappop(self.heap)
		return self.heap[0]

	def pop(self):
		self.len -= 1
		ret = heapq.heappop(self.heap)
		while ret not in self.counts:
			ret = heapq.heappop(self.heap)
		self.counts[ret] -= 1
		if self.counts[ret] == 0:
			del self.counts[ret]
		return ret

	def add(self, elem):
		self.counts[elem] += 1
		self.len += 1
		heapq.heappush(self.heap, elem)

	def remove(self, elem):
		if elem not in self.counts:
			return False
		self.len -= 1
		self.counts[elem] -= 1
		if self.counts[elem] == 0:
			del self.counts[elem]
		if self.len * 2 < len(self.heap):
			self.heap = list(self.counts.elements())
			heapq.heapify(self.heap)
		return True

def run(inputs):
	lhs = DeletableHeap()
	rhs = DeletableHeap()

	def balance_add_left():
		if lhs.len < rhs.len:
			lhs.add(-rhs.pop())

	def balance_add_right():
		if rhs.len < lhs.len - 1:
			rhs.add(-lhs.pop())
	median = 0
	for line in inputs:
		if not line:
			continue
		(command, _, n) = line.partition(' ')
		n = int(n)
		if command == 'r':
			if n <= median:
				result = lhs.remove(-n)
				balance_add_left()
			else:
				result = rhs.remove(n)
				balance_add_right()
			if not result:
				print('Wrong!')
				continue
		elif command == 'a':
			if n <= median:
				lhs.add(-n)
				balance_add_right()
			else:
				rhs.add(n)
				balance_add_left()
		else:
			raise ValueError('unexpected command')
		if lhs.len == 0:
			print('Wrong!')
			continue
		elif lhs.len > rhs.len:
			median = -lhs.head()
		else:
			median = (-lhs.head() + rhs.head()) / 2
		if median == int(median):
			print(int(median))
		else:
			print(median)
inputs = sys.stdin
next(inputs)
run(inputs)


import random

class SkipNode(object):

	def __init__(self, val, height=1):
		self.val = val
		self.height = height
		self.next = [None for _ in range(height)]
		self.length = [0 for _ in range(height)]

	def __repr__(self):
		return '<SkipNode %s>' % self.val

class SkipList(object):

	def __init__(self, height):
		self.height = height
		self.head = SkipNode(None, height)
		self.size = 0

	def _search_path_by_key(self, key):
		update = [None for _ in range(self.height)]
		node = self.head
		j = -1
		for i in reversed(range(self.height)):
			while node.next[i] and node.next[i].val < key:
				j += node.length[i]
				node = node.next[i]
			update[i] = (node, j)
		return update

	def _search_path_by_idx(self, idx):
		update = [None for _ in range(self.height)]
		node = self.head
		j = -1
		for i in reversed(range(self.height)):
			while node.next[i] and j + node.length[i] < idx:
				j += node.length[i]
				node = node.next[i]
			update[i] = (node, j)
		return update

	def update_height(self, height):
		self.height = max(self.height, height)
		while len(self.head.next) < self.height:
			self.head.next.append(None)
			self.head.length.append(0)

	def find_at(self, pos):
		update = self._search_path_by_idx(pos)
		(prev_node, _) = update[0]
		return prev_node.next[0] if prev_node is not None else None

	def find(self, key):
		update = self._search_path_by_key(key)
		(prev_node, _) = update[0]
		return prev_node.next[0] if prev_node is not None else None

	def add(self, key):
		new_node = SkipNode(key, self.random_height())
		self.update_height(new_node.height)
		update = self._search_path_by_key(key)
		pos = update[0][1]
		self._insert(pos + 1, new_node, update)

	def _insert(self, pos, new_node, update=None):
		if update is None:
			update = self._search_path_by_idx(pos)
		for level in reversed(range(self.height)):
			(prev_node, j) = update[level]
			if level < new_node.height:
				span = pos - j
				new_node.length[level] = prev_node.length[level] - span + 1
				prev_node.length[level] = span
				new_node.next[level] = prev_node.next[level]
				prev_node.next[level] = new_node
			else:
				prev_node.length[level] += 1
		self.size += 1

	def insert(self, pos, val):
		new_node = SkipNode(val, self.random_height())
		self.update_height(new_node.height)
		self._insert(pos, new_node)

	def _remove(self, pos, update=None):
		if update is None:
			update = self._search_path_by_idx(pos)
		node_to_del = update[0][0].next[0]
		for level in reversed(range(self.height)):
			(prev_node, _) = update[level]
			if level < node_to_del.height:
				prev_node.length[level] = prev_node.length[level] + node_to_del.length[level] - 1
				prev_node.next[level] = node_to_del.next[level]
			else:
				prev_node.length[level] -= 1
		self.size -= 1

	def remove_idx(self, pos):
		if pos < 0 or pos >= self.size:
			return None
		self._remove(pos)

	def remove_key(self, key):
		update = self._search_path_by_key(key)
		(prev_node, _) = update[0]
		if prev_node.next[0] is None or prev_node.next[0].val > key:
			return None
		self._remove(0, update)
		return True

	def at_idx(self, pos):
		update = self._search_path_by_idx(pos)
		(node, _) = update[0]
		return node.next[0]

	def random_height(self):
		h = 1
		while random.randint(1, 3) % 3 == 0:
			h += 1
		return h

	def to_str(self):
		for i in reversed(range(self.height)):
			node = self.head
			data = []
			while node is not None:
				data.append('%s:%d' % (node.val if node.val is not None else 'nil', node.length[i]))
				node = node.next[i]
			print('[L%d] %s' % (i, '-->'.join(data)))

def display_median(sl):
	if sl.size == 0:
		print('Wrong!')
	elif sl.size % 2 == 0:
		idx = sl.size // 2
		n1 = sl.at_idx(idx - 1).val
		n2 = sl.at_idx(idx).val
		if (n1 + n2) % 2 == 0:
			print((n1 + n2) // 2)
		else:
			m = (n1 + n2) / 2.0
			print('%.1f' % m)
	else:
		print(sl.at_idx(sl.size // 2).val)

def median(sl, x, i):
	if x == 'a':
		sl.add(i)
		display_median(sl)
	elif x == 'r':
		t = sl.remove_key(i)
		if t is None:
			print('Wrong!')
		else:
			display_median(sl)
sl = SkipList(10)
N = int(input())
for _ in range(N):
	(x, i) = input().split()
	median(sl, x, int(i))


import sys
import random

class skipnode:

	def __init__(self, value=None, prev=None, next=None):
		self.value = value
		self.next = next
		self.prev = prev
		self.down = None
		self.skip_count = 0

	def insert(self, value, skip_levels):
		if self.next is None:
			if skip_levels <= 0:
				new_node = skipnode(value, self)
				self.next = new_node
				if self.down:
					new_node.down = self.down.insert(value, skip_levels - 1)
				base_skip_distance = new_node.get_prev_base_distance()
				new_node.skip_count = self.skip_count - base_skip_distance
				self.skip_count = base_skip_distance
				return new_node
			elif self.down:
				self.skip_count += 1
				return self.down.insert(value, skip_levels - 1)
			return
		if self.next.value >= value:
			if skip_levels <= 0:
				new_node = skipnode(value, self, self.next)
				self.next.prev = new_node
				self.next = new_node
				if self.down:
					new_node.down = self.down.insert(value, skip_levels - 1)
				base_skip_distance = new_node.get_prev_base_distance()
				new_node.skip_count = self.skip_count - base_skip_distance
				self.skip_count = base_skip_distance
				return new_node
			elif self.down:
				self.skip_count += 1
				return self.down.insert(value, skip_levels - 1)
			return
		return self.next.insert(value, skip_levels)

	def find(self, value, remove=False):
		if self.value == value:
			return self
		if self.next is None:
			if self.down:
				found = self.down.find(value)
				if found:
					self.skip_count -= 1
				return found
			else:
				return None
		if value < self.next.value:
			if self.down:
				found = self.down.find(value)
				if found:
					self.skip_count -= 1
				return found
			else:
				return None
		found = self.next.find(value)
		return found

	def burn(self):
		if self.prev:
			self.prev.next = self.next
			self.prev.skip_count += self.skip_count
		if self.next:
			self.next.prev = self.prev
		if self.down:
			self.down.burn()

	def to_list(self):
		lst = [{'value': self.value, 'skip_count': self.skip_count}]
		if self.next:
			lst += self.next.to_list()
		return lst

	def find_index(self, index_at, index_to_find):
		if index_at == index_to_find:
			return self.value
		if self.next is None or index_at + 1 + self.skip_count > index_to_find:
			return self.down.find_index(index_at, index_to_find)
		if index_at + 1 + self.skip_count <= index_to_find:
			return self.next.find_index(index_at + 1 + self.skip_count, index_to_find)

	def get_prev_base_distance(self):
		prev_base_node = self.prev.get_base()
		n = prev_base_node
		distance = 0
		while n.next.value != self.value:
			distance += 1
			n = n.next
		return distance

	def get_base(self):
		n = self
		while n.down:
			n = n.down
		return n

class skippity:

	def __init__(self):
		self.height = 40
		self.root = skipnode()
		self.count = 0
		n = self.root
		for i in range(self.height - 1):
			n.down = skipnode()
			n = n.down

	def insert(self, value, level=False):
		self.count += 1
		if not level:
			level = self.get_level()
		self.root.insert(value, self.height - level)

	def find(self, value):
		return self.root.find(value)

	def remove(self, value):
		found = self.find(value)
		if found:
			found.burn()
			self.count -= 1
			return True
		return False

	def get_level(self):
		level = 1
		for i in range(self.height - 1):
			flip = bool(random.getrandbits(1))
			if not flip:
				return level
			level += 1
		return self.height

	def get_elements(self):
		n = self.root
		while n.down is not None:
			n = n.down
		return n.to_list()

	def median(self):
		if self.count == 0:
			return False
		if self.count % 2 == 1:
			return self.root.find_index(0, self.count // 2 + 1)
		else:
			median = (self.root.find_index(0, self.count // 2) + self.root.find_index(0, self.count // 2 + 1)) / 2
			if median % 1 == 0:
				return int(median)
			return median

	def debug(self, display_right_count=False):
		full_list = self.get_elements()
		full_length = len(full_list)
		n = self.root
		do_next = True
		while do_next:
			current_list = n.to_list()
			pos = 0
			for i in range(0, full_length):
				if pos < len(current_list) and full_list[i]['value'] == current_list[pos]['value']:
					if display_right_count:
						print('{:3} '.format(current_list[pos]['skip_count']), end='_')
					else:
						print('{:3} '.format(full_list[i]['value'] if full_list[i]['value'] else ''), end='_')
					pos += 1
				else:
					print('_____', end='')
			print()
			do_next = True if n.down is not None else False
			n = n.down
		print()
skip = skippity()
n = int(input())
for i in range(n):
	(command, value) = input().split()
	value = int(value)
	if command == 'a':
		skip.insert(value)
		print(skip.median())
	elif skip.remove(value):
		median = skip.median()
		if median is not False:
			print(median)
		else:
			print('Wrong!')
	else:
		print('Wrong!')


from bisect import insort, bisect

def median(arr):
	h = len(arr) // 2
	m = (arr[h] + arr[~h]) / 2
	return int(m) if m == int(m) else m
n = int(input())
values = []
for _ in range(n):
	wrong_operation = False
	(operation, num) = input().split()
	num = int(num)
	if operation == 'a':
		insort(values, num)
	else:
		index = bisect(values, num)
		if values:
			if values[index - 1] != num:
				wrong_operation = True
			else:
				del values[index - 1]
	if not values or wrong_operation:
		print('Wrong!')
	else:
		print(median(values))


import bisect
WRONG = 'Wrong!'

def get_median(arr):
	if len(arr) == 0:
		return WRONG
	mid = len(arr) // 2
	if len(arr) % 2 == 0:
		med = (arr[mid - 1] + arr[mid]) / 2
		return ('%f' % med).rstrip('0').rstrip('.')
	return str(arr[mid])

def median(a, x):
	arr = []
	for (op, val) in zip(a, x):
		if op == 'r':
			i = bisect.bisect_left(arr, val)
			if i < len(arr) and arr[i] == val:
				del arr[i]
				print(get_median(arr))
			else:
				print(WRONG)
		elif op == 'a':
			i = bisect.bisect_left(arr, val)
			arr.insert(i, val)
			print(get_median(arr))
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


import bisect

def index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return None

def median(a, x):
	l = []
	for i in range(0, len(a)):
		if a[i] == 'a':
			bisect.insort(l, int(x[i]))
			median_calculate(l)
		elif index(l, int(x[i])) is not None:
			l.remove(int(x[i]))
			median_calculate(l)
		else:
			print('Wrong!')

def median_calculate(dd):
	if len(dd) == 0:
		print('Wrong!')
		return
	elif len(dd) == 1:
		median = dd[0]
	elif len(dd) % 2 == 0:
		mid = int(len(dd) // 2) - 1
		next = mid + 1
		median = (dd[mid] + dd[next]) / 2
		if int(median) == median:
			median = int(median)
	else:
		mid = len(dd) // 2
		median = int(dd[mid])
	print(median)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from bisect import bisect

def median(a):
	n = len(a)
	c = n // 2
	if not n:
		return 'Wrong!'
	elif n % 2:
		return a[c]
	else:
		s = a[c - 1] + a[c]
		return s / 2 if s % 2 else s // 2
s = []
for _ in range(int(input())):
	(op, x) = input().strip().split(' ')
	x = int(x)
	i = bisect(s, x)
	if op == 'r':
		i = max(0, i - 1)
		if s and s[i] == x:
			del s[i]
		else:
			print('Wrong!')
			continue
	else:
		s.insert(i, x)
	print(median(s))


import sys

class Median:

	def __init__(self):
		self._values = []

	def add(self, value):
		(found, i) = self._search(value)
		self._values.insert(i, value)
		return self._median()

	def remove(self, value):
		(found, i) = self._search(value)
		if found:
			self._values.pop(i)
			return self._median()
		return 'Wrong!'

	def _median(self):
		if not self._values:
			return 'Wrong!'
		l = len(self._values)
		i = l // 2
		if l % 2 == 0:
			median = (self._values[i - 1] + self._values[i]) / 2
		else:
			median = self._values[i]
		if median == int(median):
			median = int(median)
		return median

	def _search(self, value):
		(s, e) = (0, len(self._values))
		while s < e:
			i = (s + e) // 2
			v = self._values[i]
			if value == v:
				return (True, i)
			elif value < v:
				e = i
			else:
				s = i + 1
		return (False, s)
n_cases = int(sys.stdin.readline())
median = Median()
for i in range(n_cases):
	(op, value) = sys.stdin.readline().split()
	value = int(value)
	if op == 'a':
		result = median.add(value)
	else:
		result = median.remove(value)
	print(result)


import bisect

def median(a, x):
	work = []
	work_ct = 0
	for (cmd, val) in zip(a, x):
		if cmd == 'a':
			bisect.insort(work, val)
			work_ct += 1
			print(calc(work, work_ct))
		else:
			try:
				index = find(work, val)
				work.pop(index)
				work_ct -= 1
				print(calc(work, work_ct))
			except ValueError:
				print('Wrong!')

def calc(sorted, count):
	if not count:
		raise ValueError()
	index = count // 2
	if count % 2:
		return sorted[index]
	val = (sorted[index - 1] + sorted[index]) / 2
	return round(val) if val == round(val) else val

def find(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	raise ValueError
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from math import floor, ceil
from bisect import insort, bisect
from collections import defaultdict

def median(l):
	ans = 0
	if len(l) % 2 == 0:
		ans = (l[len(l) // 2 - 1] + l[len(l) // 2]) / 2
	else:
		ans = l[len(l) // 2]
	if floor(ans) == ceil(ans):
		ans = str(int(ans))
	else:
		ans = str(ans).rstrip('0')
	return ans
N = int(input().strip())
l = []
d = defaultdict(int)
for i in range(N):
	ip = input().strip().split(' ')
	(op, x) = (ip[0], int(ip[1]))
	if op == 'a':
		insort(l, x)
		d[x] += 1
	elif d[x] == 0:
		print('Wrong!')
		continue
	else:
		l.remove(x)
		d[x] -= 1
	if len(l) == 0:
		print('Wrong!')
	else:
		print(median(l))


import heapq
import re

def heapdel(h, n):
	N = len(h)
	try:
		k = h.index(n)
	except ValueError:
		return False
	last_elem = h.pop()
	if k == N - 1:
		return True
	h[k] = last_elem
	if k == 0 or h[k] > h[(k - 1) // 2]:
		while 2 * k + 1 < N - 1:
			t = h[k]
			if 2 * k + 2 < N - 1:
				m = min(2 * k + 2, 2 * k + 1, key=lambda v: h[v])
				if t > h[m]:
					h[k] = h[m]
					h[m] = t
					k = m
				else:
					break
			elif t > h[2 * k + 1]:
				h[k] = h[2 * k + 1]
				h[2 * k + 1] = t
				k = 2 * k + 1
			else:
				break
	else:
		while k > 0 and h[k] < h[(k - 1) // 2]:
			t = h[k]
			h[k] = h[(k - 1) // 2]
			h[(k - 1) // 2] = t
			k = (k - 1) // 2
	return True

class RunningMedian:

	def __init__(self, init=[]):
		self._leh = []
		self._gh = []
		for i in init:
			self.add(i)

	def add(self, v):
		if len(self._leh) == 0 or v <= -self._leh[0]:
			h = self._leh
			v = -v
		else:
			h = self._gh
		heapq.heappush(h, v)
		self._balance()

	def remove(self, v):
		if len(self._leh) == 0:
			return False
		if v <= -self._leh[0]:
			h = self._leh
			v = -v
		else:
			h = self._gh
		ret = heapdel(h, v)
		self._balance()
		return ret

	def get_median(self):
		if len(self._leh) == 0:
			return None
		if len(self._leh) == len(self._gh):
			return (-self._leh[0] + self._gh[0]) / 2
		else:
			return -self._leh[0]

	def _balance(self):
		while len(self._leh) < len(self._gh):
			v = heapq.heappop(self._gh)
			heapq.heappush(self._leh, -v)
		while len(self._leh) - len(self._gh) > 1:
			v = heapq.heappop(self._leh)
			heapq.heappush(self._gh, -v)
n = int(input().strip())
rm = RunningMedian()
for _ in range(n):
	(i, x) = input().strip().split()
	x = int(x)
	ret = True
	if i == 'a':
		rm.add(x)
	elif i == 'r':
		ret = rm.remove(x)
	med = rm.get_median()
	if ret and med is not None:
		print(re.sub('\\.0+$', '', str(med)))
	else:
		print('Wrong!')


import bisect
(_, ARRAY, OPS) = (input(), [], {'r': lambda val: ARRAY.remove(val), 'a': lambda val: bisect.insort(ARRAY, val)})
for line in __import__('sys').stdin:
	(op, val) = line.strip().split()
	try:
		OPS[op](int(val))
		(mid, is_odd) = divmod(len(ARRAY), 2) if ARRAY else 1 / 0
		median = ARRAY[mid] if is_odd else sum(ARRAY[mid - 1:mid + 1]) / 2
		print(int(median) if float(median).is_integer() else median)
	except (ValueError, ZeroDivisionError):
		print('Wrong!')


import bisect
import decimal
lst = list()

def median():
	leng = len(lst)
	if leng == 0:
		print('Wrong!')
		return
	mid = leng // 2
	if leng % 2 != 0:
		print(lst[mid])
	else:
		x = lst[mid]
		y = lst[mid - 1]
		print(('%f' % decimal.Decimal((int(x) + int(y)) / 2)).rstrip('0').rstrip('.'))
N = int(input())
for _ in range(N):
	(q, e) = input().strip().split(' ')
	e = int(e)
	if q == 'r':
		x = bisect.bisect_left(lst, e)
		if x < len(lst) and lst[x] == e:
			lst.pop(x)
			median()
		else:
			print('Wrong!')
	else:
		bisect.insort_left(lst, e)
		median()


class ElementNotFoundError(Exception):
	pass

class EmptyHeap(ElementNotFoundError):
	pass

class Heap(object):

	def __init__(self):
		self.data = []
		self.d = dict()

	def __len__(self):
		return len(self.data)

	def __str__(self):
		return str(self.data)

	def nearest_top(self, x):
		raise NotImplementedError

	def swap(self, i, j):
		if i == j:
			return
		if self.data[i] != self.data[j]:
			self.d[self.data[i]].remove(i)
			self.d[self.data[j]].remove(j)
			self.d[self.data[i]].add(j)
			self.d[self.data[j]].add(i)
			(self.data[i], self.data[j]) = (self.data[j], self.data[i])

	def parent(self, x):
		return (x - 1) // 2

	def children(self, x):
		return list(range(2 * x + 1, min(2 * x + 3, len(self))))

	def top(self):
		if not self:
			raise EmptyHeap()
		return self.data[0]

	def remove_back_element(self):
		retval = self.data.pop()
		if len(self.d[retval]) > 1:
			self.d[retval].remove(len(self))
		else:
			del self.d[retval]
		return retval

	def pop_top(self):
		if not self:
			raise EmptyHeap()
		self.swap(0, len(self) - 1)
		retval = self.remove_back_element()
		if self:
			self.fall_from(0)
		return retval

	def fall_from(self, i):
		while True:
			x = self.nearest_top([i] + self.children(i))
			if x == i:
				break
			self.swap(i, x)
			i = x
		return i

	def add(self, x):
		if x in self.d:
			self.d[x].add(len(self))
		else:
			self.d[x] = {len(self)}
		self.data.append(x)
		i = len(self) - 1
		self.float_up(i)

	def float_up(self, i):
		while i > 0:
			parent = self.parent(i)
			x = self.nearest_top([i, parent])
			if x != i:
				break
			self.swap(i, parent)
			i = parent
		return i

	def remove(self, x):
		try:
			i = next(iter(self.d[x]))
		except KeyError:
			raise ElementNotFoundError()
		self.swap(i, len(self) - 1)
		retval = self.remove_back_element()
		if i >= len(self):
			return
		j = self.float_up(i)
		self.fall_from(j)

class MinHeap(Heap):

	def nearest_top(self, x):
		return min(x, key=lambda x: self.data[x])

class MaxHeap(Heap):

	def nearest_top(self, x):
		return max(x, key=lambda x: self.data[x])

class MedianHeap(object):

	def __init__(self):
		self.large = MinHeap()
		self.small = MaxHeap()

	def __len__(self):
		return len(self.large) + len(self.small)

	def __str__(self):
		return str(self.small) + '---' + str(self.large)

	def balance(self):
		while len(self.large) - len(self.small) > 1:
			x = self.large.pop_top()
			self.small.add(x)
		while len(self.small) - len(self.large) > 1:
			x = self.small.pop_top()
			self.large.add(x)

	def median(self):
		if len(self.large) > len(self.small):
			return self.large.top()
		elif len(self.large) < len(self.small):
			return self.small.top()
		else:
			total = self.large.top() + self.small.top()
			if total % 2:
				return total / 2
			else:
				return total // 2

	def add(self, x):
		if not self or x <= self.median():
			self.small.add(x)
		else:
			self.large.add(x)
		self.balance()

	def remove(self, x):
		if self.small and x <= self.small.top():
			self.small.remove(x)
		else:
			self.large.remove(x)
		self.balance()

def main(argv):
	m = MedianHeap()
	n = int(input())
	for _ in range(n):
		(instruction, x) = input().split()
		x = int(x)
		if instruction == 'a':
			m.add(x)
			print('{}'.format(m.median()))
		elif instruction == 'r':
			try:
				m.remove(x)
				try:
					print('{}'.format(m.median()))
				except EmptyHeap:
					print('Wrong!')
			except ElementNotFoundError:
				print('Wrong!')
import sys
main(sys.argv)


import bisect

class Numbers:

	def __init__(self):
		self.lst = []

	def add(self, val):
		bisect.insort(self.lst, val)

	def remove(self, val):
		pos = bisect.bisect_left(self.lst, val)
		if pos == len(self.lst) or self.lst[pos] != val:
			return None
		self.lst.pop(pos)
		return val

	def printMedian(self):
		size = len(self.lst)
		if size == 0:
			print('Wrong!')
		else:
			(pos, remain) = divmod(size, 2)
			median1 = self.lst[pos]
			if remain != 0:
				print(median1)
			else:
				median2 = self.lst[pos - 1]
				(median, remn) = divmod(median2 + median1, 2)
				if remn == 0:
					print(median)
				elif median == -1:
					print('-0.5')
				else:
					if median < -1:
						median += 1
					print(str(median) + '.5')

def median(a, x):
	lst = Numbers()
	for (aa, xx) in zip(a, x):
		if aa == 'a':
			lst.add(xx)
			lst.printMedian()
		elif lst.remove(xx) is None:
			print('Wrong!')
		else:
			lst.printMedian()
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from bisect import *

def median(list):
	nl = len(list)
	nnl = int(nl / 2)
	m = 0
	mod = 0
	if nl % 2 == 0:
		v = list[nnl - 1] + list[nnl]
		mod = v % 2
		m = v / 2
	else:
		m = list[nnl]
	if mod == 0:
		print('%d' % m)
	else:
		print(m)
n = int(input())
list = []
for a in range(n):
	line = input().strip().split(' ')
	num = int(line[1])
	if line[0] == 'a':
		insort(list, num)
		median(list)
	else:
		try:
			pos = bisect_left(list, num)
			if list[pos] == num:
				del list[pos]
				leng = len(list)
			else:
				leng = -1
			if leng <= 0:
				print('Wrong!')
			else:
				median(list)
		except ValueError:
			print('Wrong!')
		except IndexError:
			print('Wrong!')


from bisect import bisect_left, insort

def print_median(li):
	sz = len(li)
	mid = sz // 2
	if sz % 2 == 1:
		median = li[mid]
	else:
		median = (li[mid - 1] + li[mid]) / 2
	m = str(median)
	if '.' in m:
		print(str(median).rstrip('0').rstrip('.'))
	else:
		print(m)

def median(a, x):
	li = []
	for (op, n) in zip(a, x):
		if op == 'a':
			insort(li, n)
			print_median(li)
		else:
			idx = bisect_left(li, n)
			if li == []:
				print('Wrong!')
			elif len(li) <= idx:
				print('Wrong!')
			elif li[idx] != n:
				print('Wrong!')
			else:
				li.pop(idx)
				if li == []:
					print('Wrong!')
				else:
					print_median(li)

def main():
	N = int(input())
	s = []
	x = []
	for i in range(0, N):
		tmp = input().strip().split(' ')
		(a, b) = [xx for xx in tmp]
		s.append(a)
		x.append(int(b))
	median(s, x)
main()


ops = []
keys = set()
for _ in range(int(input())):
	(c, x) = input().split()
	x = int(x)
	assert c == 'a' or c == 'r'
	keys.add(x)
	ops.append((c, x))
keys = sorted(keys)

def maketree(keys):
	if len(keys) == 0:
		return None
	mid = len(keys) // 2
	return [maketree(keys[:mid]), keys[mid], 0, 0, maketree(keys[mid + 1:])]

def size(tree):
	return 0 if tree == None else tree[3]

def add(tree, x):
	d = x - tree[1]
	if d == 0:
		tree[2] += 1
	else:
		add(tree[(d > 0) * 4], x)
	tree[3] += 1

def find(tree, k):
	l = size(tree[0])
	if k < l:
		return find(tree[0], k)
	elif k < l + tree[2]:
		return tree[1]
	else:
		return find(tree[4], k - l - tree[2])

def remove(tree, x):
	d = x - tree[1]
	if d == 0:
		if tree[2] == 0:
			return False
		tree[2] -= 1
		tree[3] -= 1
		return True
	else:
		worked = remove(tree[(d > 0) * 4], x)
		if worked:
			tree[3] -= 1
		return worked

def median2(tree):
	n = size(tree)
	if n == 0:
		return None
	elif n % 2 == 1:
		return 2 * find(tree, (n - 1) // 2)
	else:
		return find(tree, n // 2) + find(tree, (n - 2) // 2)
tree = maketree(keys)
for (c, x) in ops:
	if c == 'a':
		add(tree, x)
	elif not remove(tree, x):
		print('Wrong!')
		continue
	if size(tree) == 0:
		print('Wrong!')
	else:
		m = median2(tree)
		print(m // 2 if m % 2 == 0 else m / 2)


from bisect import bisect_left as bl

def getMedian(l, le):
	if le == 0:
		return 'Wrong!'
	if le % 2 == 0:
		c = int(le / 2)
		ans = l[c - 1] + l[c]
		if ans % 2 == 0:
			return int(ans / 2)
		return ans / 2
	else:
		return l[int(le / 2)]
n = int(input())
l = []
le = len(l)
for _ in range(n):
	s = input().split()
	com = s[0]
	num = int(s[1])
	if com == 'a':
		ind = bl(l, num)
		if ind == le:
			l.append(num)
			le += 1
		else:
			l.insert(ind, num)
			le += 1
		print(getMedian(l, le))
	else:
		ind = bl(l, num)
		if ind == le or l[ind] != num:
			print('Wrong!')
			continue
		else:
			l.pop(ind)
			le -= 1
			print(getMedian(l, le))


from bisect import insort
from collections import defaultdict
N = int(input())
a = []
myDict = defaultdict(int)
for i in range(N):
	(q, val) = input().strip().split(' ')
	val = int(val)
	if q == 'r':
		if myDict[val] == 0:
			print('Wrong!')
		else:
			myDict[val] -= 1
			a.remove(val)
			size = len(a)
			if size == 0:
				print('Wrong!')
			elif size % 2 == 1:
				print(a[size // 2])
			else:
				mid = (a[size // 2] + a[size // 2 - 1]) / 2.0
				if mid == int(mid):
					mid = int(mid)
				print(mid)
	else:
		insort(a, val)
		size = len(a)
		myDict[val] += 1
		if size % 2 == 1:
			print(a[size // 2])
		else:
			mid = (a[size // 2] + a[size // 2 - 1]) / 2.0
			if mid == int(mid):
				mid = int(mid)
			print(mid)


from bisect import insort, bisect_left
from collections import defaultdict
from pprint import pprint
N = int(input())
arr = []
myDict = {}
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	if a == 'r':
		b = int(b)
		if b in myDict:
			if myDict[b] > 0:
				del arr[bisect_left(arr, b)]
				myDict[b] -= 1
			else:
				myDict.pop(b)
				print('Wrong!')
				continue
		else:
			print('Wrong!')
			continue
	if a == 'a':
		b = int(b)
		insort(arr, b)
		if b in myDict:
			myDict[b] += 1
		else:
			myDict[b] = 1
	if len(arr) == 0:
		print('Wrong!')
	elif len(arr) > 0:
		if len(arr) % 2 == 0:
			mid = len(arr) // 2
			mid_pre = mid - 1
			if (arr[mid] + arr[mid_pre]) % 2 == 0:
				print(int((float(arr[mid]) + float(arr[mid_pre])) / 2.0))
			else:
				print((float(arr[mid]) + float(arr[mid_pre])) / 2.0)
		else:
			mid = len(arr) // 2
			print(int(arr[mid]))


import random
danger = 0

def connect(a, b, location):
	if a is not None and b is not None:
		a.child[location] = b
		b.prev = a
		b.loc = location
	elif a is not None:
		a.child[location] = None
	elif b is not None:
		(b.prev, b.loc) = (None, None)
	else:
		pass

class Node:

	def __init__(self, treedata, heapdata, prev=None, location=None):
		self.treedata = treedata
		self.heapdata = heapdata
		self.child = [None, None]
		self.prev = prev
		self.loc = location
		if prev is not None:
			self.prev.child[location] = self

	def __repr__(self):
		return str(self.treedata) + ', ' + str(self.heapdata)[:5]

	def rotate(self):
		a = self
		b = self.prev
		c = b.prev
		l1 = a.loc
		l2 = b.loc
		d = a.child[1 - l1]
		connect(a, b, 1 - l1)
		connect(b, d, l1)
		connect(c, a, l2)

	def display(self):
		if self.left:
			print('left =', self.left.treedata, self.left.heapdata)
		if self.right:
			print('right =', self.right.treedata, self.right.heapdata)

class Treap:

	def __init__(self):
		self.root = None
		self.length = 0

	def pop(self, direction):
		self.length -= 1
		d = direction
		z = None
		x = self.root
		y = self.root.child[d]
		while y is not None:
			(z, x, y) = (x, y, y.child[d])
		connect(z, x.child[1 - d], d)
		if z is None:
			self.root = x.child[1 - d]
		return x.treedata

	def append(self, number):
		rand = random.random()
		newobject = Node(number, rand)
		self.length += 1
		x = self.root
		flag = None
		z = None
		while not x is None:
			if number < x.treedata:
				flag = 0
			else:
				flag = 1
			(x, z) = (x.child[flag], x)
		connect(z, newobject, flag)
		while newobject.prev is not None and rand < newobject.prev.heapdata:
			newobject.rotate()
		if newobject.prev is None:
			self.root = newobject

	def noderemove(self, node):
		newthing = None
		flag = False
		if node is self.root:
			flag = True
		while node.child != [None, None]:
			(y0, y1) = (node.child[0], node.child[1])
			if y0 is not None and y1 is not None:
				if y0.heapdata < y1.heapdata:
					newthing = y0
					prevloc = 0
				else:
					newthing = y1
					prevloc = 1
			elif y0 is not None:
				newthing = y0
				prevloc = 0
			else:
				newthing = y1
				prevloc = 1
			newthing.rotate()
			if flag:
				self.root = newthing
				flag = False
		if newthing is not None:
			newthing.child[1 - prevloc] = None
		elif self.root == node:
			self.root = None
		else:
			node.prev.child[node.loc] = None

	def remove(self, number):
		x = self.root
		if x is None:
			return False
		while x.treedata != number:
			if x.treedata > number:
				y = x.child[0]
			else:
				y = x.child[1]
			if y is not None:
				x = y
			else:
				return False
		self.length -= 1
		self.noderemove(x)
		return True

	def display(self):
		(x, y, z) = (self.root, None, None)
		if x:
			(y, z) = (x.child[0], x.child[1])
			x = (x.treedata, x.heapdata)
			if y:
				y = (y.treedata, y.heapdata)
			if z:
				z = (z.treedata, z.heapdata)
		print(x, y, z, self.length)

class MedianFinder:

	def __init__(self):
		lefttree = Treap()
		righttree = Treap()
		self.trees = [lefttree, righttree]
		self.center = []
		self.size = 0

	def median(self):
		if len(self.center) == 0:
			return 'Wrong!'
		number = sum(self.center) / len(self.center)
		if number == int(number):
			number = int(number)
		return number

	def append(self, number):
		self.size += 1
		if len(self.center) == 1:
			n = self.center[0]
			if number == n:
				self.center.append(number)
				return number
			if number > n:
				direction = 1
			if number < n:
				direction = 0
			self.trees[direction].append(number)
			self.center.append(self.trees[direction].pop(1 - direction))
			self.center.sort()
		else:
			self.center.append(number)
			self.center.sort()
			if len(self.center) == 3:
				(x, y, z) = self.center
				self.trees[0].append(x)
				self.trees[1].append(z)
				self.center = [y]
		return self.median()

	def remove(self, number):
		if self.size == 0:
			return 'Wrong!'
		if number in self.center:
			self.center.remove(number)
			self.size -= 1
			if not self.center:
				if self.size != 0:
					self.center = [self.trees[0].pop(1), self.trees[1].pop(0)]
			return self.median()
		if number < self.center[0]:
			direction = 0
		elif number > self.center[-1]:
			direction = 1
		else:
			return 'Wrong!'
		if self.trees[direction].remove(number):
			self.size -= 1
			if len(self.center) == 2:
				self.trees[direction].append(self.center[direction])
				n = self.center[1 - direction]
				self.center = [n]
				return n
			else:
				self.center.append(self.trees[1 - direction].pop(direction))
				self.center.sort()
				return self.median()
		else:
			return 'Wrong!'
N = int(input())
work = MedianFinder()
for _ in range(N):
	(a, b) = input().split()
	b = int(b)
	if a == 'r':
		print(work.remove(b))
	else:
		print(work.append(b))


import math
import random

class skipnode:

	def __init__(self, val, size):
		self.val = val
		self.next = [None] * size
		self.count = [1] * size

class skiplist:

	def __init__(self, size):
		self.size = math.ceil(math.log2(size))
		self.count = 0
		self.head = skipnode(None, self.size)

	def __len__(self):
		return self.count

	def insert(self, val):
		self.count += 1
		n = min(1 - math.ceil(math.log2(1 - random.random())), self.size)
		node = skipnode(val, n)
		skip = self.head
		for i in range(self.size - 1, n - 1, -1):
			while True:
				next = skip.next[i]
				if next == None or next.val >= val:
					break
				skip = next
			skip.count[i] += 1
		mid = skip
		pos = 1
		for i in range(n - 1, -1, -1):
			while True:
				next = skip.next[i]
				if next == None or next.val >= val:
					break
				pos += skip.count[i]
				skip = next
		skip = mid
		for i in range(n - 1, -1, -1):
			while True:
				next = skip.next[i]
				if next == None or next.val >= val:
					break
				pos -= skip.count[i]
				skip = next
			node.next[i] = next
			node.count[i] = skip.count[i] - pos + 1
			skip.next[i] = node
			skip.count[i] = pos

	def delete(self, val):
		skip = self.head
		for i in range(self.size - 1, -1, -1):
			while True:
				next = skip.next[i]
				if next == None or next.val >= val:
					break
				skip = next
			if next != None and next.val == val:
				break
		else:
			return False
		self.count -= 1
		skip = self.head
		for i in range(self.size - 1, -1, -1):
			while True:
				next = skip.next[i]
				if next == None or next.val >= val:
					break
				skip = next
			if next != None and next.val == val:
				skip.count[i] += next.count[i] - 1
				skip.next[i] = next.next[i]
			else:
				skip.count[i] -= 1
		return True

	def median(self):
		n = (self.count + 1) // 2
		skip = self.head
		for i in range(self.size - 1, -1, -1):
			while skip.count[i] <= n:
				n -= skip.count[i]
				skip = skip.next[i]
		if self.count & 1:
			return skip.val
		else:
			return (skip.val + skip.next[0].val) / 2
N = int(input())
skip = skiplist(10 ** 5)
for n in range(N):
	(op, val) = input().split()
	val = int(val)
	if op == 'a':
		skip.insert(val)
		good = True
	elif op == 'r':
		good = skip.delete(val)
	if good and len(skip) > 0:
		print('{:.20g}'.format(skip.median()))
	else:
		print('Wrong!')


from bisect import bisect_left

def binary_search(lst, x):
	m = bisect_left(lst, x, 0, len(lst))
	return m

def median(lst):
	x = len(lst)
	if x == 0:
		return 'Wrong!'
	if x % 2 == 0:
		m = (lst[x // 2] + lst[x // 2 - 1]) / 2
	else:
		m = lst[x // 2]
	return ('%f' % m).rstrip('0').rstrip('.')

def main():
	nums = []
	k = int(input())
	for i in range(k):
		(operation, n) = input().split()
		n = int(n)
		idx = binary_search(nums, n)
		if operation == 'r':
			if idx >= len(nums) or nums[idx] != n:
				print('Wrong!')
				continue
			else:
				nums.pop(idx)
		elif operation == 'a':
			nums.insert(idx, n)
		print(median(nums))
main()


from collections import defaultdict
from bisect import insort_left, bisect_left
from math import ceil, floor

def median(s, x):
	with open('2_Output_Median_Updates_Try.txt', 'a+') as f:
		a = []
		defdic = defaultdict(int)
		for i in range(len(s)):
			if s[i] == 'r':
				if defdic[x[i]] == 0:
					print('Wrong!')
					continue
				else:
					ind = bisect_left(a, x[i])
					del a[ind]
					defdic[x[i]] -= 1
			elif s[i] == 'a':
				insort_left(a, x[i])
				defdic[x[i]] += 1
			index = (len(a) - 1) / 2
			i1 = int(floor(index))
			i2 = int(ceil(index))
			if len(a) == 0:
				print('Wrong!')
			elif i1 == i2:
				print(a[i1])
			else:
				print(str((a[i1] + a[i2]) / 2).rstrip('0').rstrip('.'))
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)


from bisect import bisect_left

def binary_search(lst, x):
	m = bisect_left(lst, x, 0, len(lst))
	return m

def median(lst):
	x = len(lst)
	if x == 0:
		return 'Wrong!'
	if x % 2 == 0:
		m = (lst[x // 2] + lst[x // 2 - 1]) / 2
	else:
		m = lst[x // 2]
	return ('%f' % m).rstrip('0').rstrip('.')

def main():
	nums = []
	k = int(input())
	for i in range(k):
		(operation, n) = input().split()
		n = int(n)
		idx = binary_search(nums, n)
		if operation == 'r':
			if idx >= len(nums) or nums[idx] != n:
				print('Wrong!')
				continue
			else:
				nums.pop(idx)
		elif operation == 'a':
			nums.insert(idx, n)
		print(median(nums))
main()


from bisect import bisect, insort

def p_median(li):
	half = len(li) // 2
	if len(li) % 2 == 1:
		print(li[half])
	else:
		(a, b) = (li[half - 1], li[half])
		temp = (a + b) / 2
		if temp % 1 == 0:
			temp = int(temp)
		print(temp)

def median(a, x):
	li = []
	for (ai, xi) in zip(a, x):
		if ai == 'a':
			insort(li, xi)
			p_median(li)
		else:
			pos = bisect(li, xi)
			if not li or li[pos - 1] != xi:
				print('Wrong!')
			else:
				li.pop(pos - 1)
				if not li:
					print('Wrong!')
				else:
					p_median(li)
N = int(input())
s = []
x = []
for i in range(0, N):
	tmp = input().strip().split(' ')
	(a, b) = [xx for xx in tmp]
	s.append(a)
	x.append(int(b))
median(s, x)