The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then:

If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set $\{1,2,3\}$, $2$ is the median.
If your set contains an even number of elements, the median is the average of the two middle elements of the sorted sample. In the sorted set $\{1,2,3,4\}$, $\frac{2+3}{2}=2.5$ is the median.

Given an input stream of $n$ integers, perform the following task for each $i^{\mbox{th}}$ integer:

Add the $i^{\mbox{th}}$ integer to a running list of integers.
Find the median of the updated list (i.e., for the first element through the $i^{\mbox{th}}$ element).
Print the updated median on a new line. The printed value must be a double-precision number scaled to $1$ decimal place (i.e., $12.3$ format).  

Example 

$a=[7,3,5,2]$  

Sorted          Median
[7]             7.0
[3, 7]          5.0
[3, 5, 7]       5.0
[2, 3, 5, 7]    4.0
  
Each of the median values is stored in an array and the array is returned for the main function to print.  

Note:  Add formatting to the print statement.  

Function Description 

Complete the runningMedian function in the editor below.  

runningMedian has the following parameters: 

- int a[n]: an array of integers  

Returns 

- float[n]: the median of the array after each insertion, modify the print statement in main to get proper formatting.    

Input Format

The first line contains a single integer, $n$, the number of integers in the data stream. 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains an integer, $a[i]$, to be inserted into the list.

Constraints

$1\leq n\leq10^5$  
$0\leq a[i]\leq10^5$

Sample Input
STDIN   Function
-----   --------
6       a[] size n = 6
12      a = [12, 4, 5, 3, 8, 7]
4
5
3
8
7

Sample Output
12.0
8.0
5.0
4.5
5.0
6.0

Explanation

There are $n=6$ integers, so we must print the new median on a new line as each integer is added to the list:

$list=\{12\},median=12.0$
$list=\{4,12\},\textit{median}=\frac{4+12}{2}=8.0$
$list=\{4,5,12\},\textit{median}=5.0$
$list=\{3,4,5,12\},\textit{median}=\frac{4+5}{2}=4.5$
$list=\{3,4,5,8,12\},\textit{median}=5.0$
$list=\{3,4,5,7,8,12\},\textit{median}=\frac{5+7}{2}=6.0$

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import heapq
(L, H) = ([], [])
for _ in range(int(input())):
	a = int(input())
	if not H:
		heapq.heappush(H, a)
	elif len(H) > len(L):
		if H[0] < a:
			b = heapq.heappushpop(H, a)
			heapq.heappush(L, -b)
		else:
			heapq.heappush(L, -a)
	elif -L[0] > a:
		b = -heapq.heappushpop(L, -a)
		heapq.heappush(H, b)
	else:
		heapq.heappush(H, a)
	if len(H) > len(L):
		print('%.1f' % H[0])
	else:
		print('%.1f' % ((H[0] - L[0]) / 2))


def left_child(k):
	return 2 * k + 1

def right_child(k):
	return 2 * k + 2

def parent(k):
	return (k - (2 if k % 2 == 0 else 1)) // 2

def swap(heap, j, k):
	(heap[j], heap[k]) = (heap[k], heap[j])

def push(heap, val):
	heap.append(val)
	siftdown(heap)

def pop(heap):
	k = len(heap) - 1
	swap(heap, 0, k)
	result = heap.pop()
	siftup(heap)
	return result

def peek(heap):
	return heap[0]

def siftdown(heap):
	child = len(heap) - 1
	p = parent(child)
	while child > 0:
		if heap[p] > heap[child]:
			swap(heap, p, child)
			(child, p) = (p, parent(p))
		else:
			break

def siftup(heap):
	size = len(heap)
	p = 0
	(l, r) = (left_child(p), right_child(p))
	while r < size:
		c = l if heap[l] < heap[r] else r
		if heap[c] < heap[p]:
			swap(heap, c, p)
			p = c
			(l, r) = (left_child(p), right_child(p))
		else:
			break
	if l < size and heap[l] < heap[p]:
		swap(heap, l, p)
(max_heap, min_heap) = ([], [])
max_heap_size = min_heap_size = 0
median = 0
n = int(input())
for _ in range(n):
	val = int(input())
	if val > median:
		push(min_heap, val)
		min_heap_size += 1
	else:
		push(max_heap, -val)
		max_heap_size += 1
	if min_heap_size > max_heap_size + 1:
		push(max_heap, -pop(min_heap))
		max_heap_size += 1
		min_heap_size -= 1
	elif max_heap_size > min_heap_size + 1:
		push(min_heap, -pop(max_heap))
		min_heap_size += 1
		max_heap_size -= 1
	if min_heap_size < max_heap_size:
		median = -float(peek(max_heap))
	elif max_heap_size < min_heap_size:
		median = float(peek(min_heap))
	else:
		median = (peek(min_heap) - peek(max_heap)) / 2.0
	print(median)


import bisect

def median(a, n):
	mid = int(n / float(2))
	if n % 2:
		return a[mid]
	else:
		return (a[mid] + a[mid - 1]) / float(2)
mylist = list()
k = int(input())
for i in range(1, k + 1):
	bisect.insort_left(mylist, int(input()))
	print(median(mylist, i))


def find_median(ls):
	t_res = []
	order_l = []
	for (i, item) in enumerate(ls):
		if i == 0:
			order_l.append(item)
		elif item >= order_l[-1]:
			order_l.append(item)
		elif item <= order_l[0]:
			order_l.insert(0, item)
		else:
			length = len(order_l)
			(low, high, res) = (0, length - 1, -1)
			while high >= low:
				middle = (high + low) // 2
				if order_l[middle] == item:
					res = middle
					break
				if order_l[middle] > item:
					if order_l[middle - 1] < item:
						res = middle
						break
					high = middle - 1
				if order_l[middle] < item:
					if order_l[middle + 1] > item:
						res = middle + 1
						break
					low = middle + 1
			order_l.insert(res, item)
		length = len(order_l)
		if length % 2 == 1:
			middle = order_l[length // 2]
		else:
			middle = (order_l[length // 2] + order_l[length // 2 - 1]) / 2
		t_res.append('{:.1f}'.format(middle))
	return t_res
n = int(input())
res = []
for _ in range(n):
	res.append(int(input()))
m_res = find_median(res)
for i in m_res:
	print(i)


tests = int(input())
import heapq
lowerThanMedian = []
higherThanMedian = []
median = 0

def putInMaxHeap(val):
	heapq.heappush(lowerThanMedian, -1 * val)

def getFromMaxHeap():
	val = heapq.heappop(lowerThanMedian)
	return -1 * val
for i in range(0, tests):
	newInt = int(input())
	if newInt >= median:
		heapq.heappush(higherThanMedian, newInt)
	else:
		putInMaxHeap(newInt)
	if abs(len(lowerThanMedian) - len(higherThanMedian)) > 1:
		if len(lowerThanMedian) > len(higherThanMedian):
			heapq.heappush(higherThanMedian, getFromMaxHeap())
		else:
			putInMaxHeap(heapq.heappop(higherThanMedian))
	if (len(lowerThanMedian) + len(higherThanMedian)) % 2 == 0:
		median = (lowerThanMedian[0] * -1 + higherThanMedian[0]) / 2
	elif len(lowerThanMedian) > len(higherThanMedian):
		median = lowerThanMedian[0] * -1
	else:
		median = higherThanMedian[0]
	print(median)


import heapq, math
from heapq import heappush
from heapq import heappop
N = int(input())
maxH = []
heappush(maxH, 100000)
minH = []
heappush(minH, 0)
for n in range(0, N):
	i = int(input())
	if i > maxH[0]:
		heappush(maxH, i)
	else:
		heappush(minH, -1 * i)
	diff = len(maxH) - len(minH)
	if diff == 2:
		i = heappop(maxH)
		heappush(minH, -1 * i)
		diff = 0
	elif diff == -1:
		i = heappop(minH)
		heappush(maxH, -1 * i)
		diff = 1
	if diff == 0:
		print((maxH[0] - minH[0]) / 2.0)
	else:
		print(maxH[0] / 1.0)


import bisect
col = []
for i in range(int(input())):
	bisect.insort_left(col, int(input()))
	mid = len(col) // 2
	values = col[mid - i % 2:mid + 1]
	print(sum(values) / len(values))


class Heap:

	def __init__(self, is_min=True):
		self.data = []
		self.is_min = is_min

	def compare(self, i, j):
		if self.is_min:
			return self.data[i] < self.data[j]
		else:
			return self.data[i] > self.data[j]

	def __getitem__(self, i):
		return self.data[i]

	def __bool__(self):
		return bool(self.size)

	def swim(self, i):
		while i != 0 and i // 2 >= 0:
			j = i // 2
			if i % 2 == 0:
				j -= 1
			if self.compare(j, i):
				break
			(self.data[i], self.data[j]) = (self.data[j], self.data[i])
			i = j

	def sink(self, i):
		l = len(self.data)
		while 2 * i + 1 < l:
			next = 2 * i + 1
			if next + 1 < l and self.compare(next + 1, next):
				next = next + 1
			if self.compare(i, next):
				break
			(self.data[i], self.data[next]) = (self.data[next], self.data[i])
			i = next

	def pop(self):
		(self.data[0], self.data[self.size - 1]) = (self.data[self.size - 1], self.data[0])
		ret = self.data.pop()
		self.sink(0)
		return ret

	def append(self, n):
		self.data.append(n)
		self.swim(len(self.data) - 1)

	@property
	def size(self):
		return len(self.data)
n = int(input())
min_heap = Heap(True)
max_heap = Heap(False)
for i in range(n):
	d = int(input())
	if not min_heap or d > min_heap[0]:
		min_heap.append(d)
	else:
		max_heap.append(d)
	if min_heap.size > max_heap.size + 1:
		max_heap.append(min_heap.pop())
	elif max_heap.size > min_heap.size + 1:
		min_heap.append(max_heap.pop())
	if min_heap.size == max_heap.size:
		median = float(min_heap[0] + max_heap[0]) / 2
	elif min_heap.size > max_heap.size:
		median = min_heap[0]
	else:
		median = max_heap[0]
	print('{:.1f}'.format(median))


import bisect

def getLast(l):
	return l[len(l) - 1]

def getFirst(l):
	return l[0]

def getAbsSizeDiff(minHeap, maxHeap):
	return abs(len(minHeap) - len(maxHeap))

def rebalance(minHeap, maxHeap):
	if len(minHeap) > len(maxHeap):
		while getAbsSizeDiff(minHeap, maxHeap) > 1:
			num = minHeap.pop(len(minHeap) - 1)
			bisect.insort(maxHeap, num)
	else:
		while getAbsSizeDiff(minHeap, maxHeap) > 1:
			num = maxHeap.pop(0)
			bisect.insort(minHeap, num)

def calcMedian(minHeap, maxHeap):
	if getAbsSizeDiff(minHeap, maxHeap) > 1:
		rebalance(minHeap, maxHeap)
	lst = []
	if len(minHeap) > len(maxHeap):
		median = getLast(minHeap)
	elif len(minHeap) < len(maxHeap):
		median = getFirst(maxHeap)
	else:
		median = (getLast(minHeap) + getFirst(maxHeap)) / 2.0
	return median

def main():
	n = int(input())
	minHeap = []
	maxHeap = []
	median = None
	for i in range(n):
		numToAdd = int(input())
		if median is None:
			minHeap.append(numToAdd)
			median = numToAdd
		else:
			if numToAdd > median:
				bisect.insort(maxHeap, numToAdd)
			else:
				bisect.insort(minHeap, numToAdd)
			median = calcMedian(minHeap, maxHeap)
		print(median)
main()


from heapq import heappush, heappop
n = int(input())
min_heap = []
max_heap = []

def add_to_heaps(num):
	if len(min_heap) == 0 and len(max_heap) == 0:
		heappush(min_heap, num)
	elif len(max_heap) == 0:
		if num < min_heap[0]:
			heappush(max_heap, -num)
		else:
			tmp = heappop(min_heap)
			heappush(max_heap, -tmp)
			heappush(min_heap, num)
	else:
		if num >= min_heap[0]:
			heappush(min_heap, num)
		elif num < min_heap[0] and num > -max_heap[0]:
			if len(min_heap) >= len(max_heap):
				heappush(max_heap, -num)
			else:
				heappush(min_heap, num)
		elif num <= -max_heap[0]:
			heappush(max_heap, -num)
		if len(max_heap) - len(min_heap) > 0:
			heappush(min_heap, -heappop(max_heap))
		elif len(min_heap) - len(max_heap) > 1:
			heappush(max_heap, -heappop(min_heap))
	assert 0 <= len(min_heap) - len(max_heap) <= 1
for i in range(n):
	num = int(input())
	add_to_heaps(num)
	if len(min_heap) > len(max_heap):
		median = float(min_heap[0])
	else:
		assert len(min_heap) == len(max_heap)
		median = (min_heap[0] - max_heap[0]) / 2
	print(median)


import array
import sys
import math

def nice_print(x):
	print('%.1f' % x)

def bisect_insert(a, left, right, x):
	the_range = right - left
	middle = int(math.floor(the_range / 2)) + left
	if a[middle] == x:
		a.insert(middle, x)
	elif a[middle] < x:
		if the_range == 0:
			a.insert(middle, x)
		elif the_range == 1:
			a.insert(middle + 1, x)
		else:
			bisect_insert(a, middle, right, x)
	elif the_range == 0:
		a.insert(max(0, middle - 1), x)
	elif the_range == 1:
		a.insert(max(0, middle - 2), x)
	else:
		bisect_insert(a, left, middle, x)

def do():
	n_numbers = int(sys.stdin.readline()) - 1
	a = array.array('d')
	n = int(sys.stdin.readline())
	a.append(n)
	nice_print(n)
	while n_numbers > 0:
		n = int(sys.stdin.readline())
		bisect_insert(a, 0, len(a), n)
		m = 0
		if len(a) % 2 == 0:
			prev = len(a) // 2 - 1
			next = prev + 1
			m = (a[prev] + a[next]) / 2
		else:
			pos = len(a) // 2
			m = a[pos]
		nice_print(m)
		n_numbers -= 1
do()


import heapq as hq
minheap = []
maxheap = []
N = int(input())
for i in range(0, N):
	x = int(input())
	if i % 2 == 0:
		hq.heappush(maxheap, -1 * x)
		if len(minheap) == 0:
			x = -1 * maxheap[0]
			print(float(x))
			continue
		elif -1 * maxheap[0] > minheap[0]:
			toMin = -1 * hq.heappop(maxheap)
			toMax = hq.heappop(minheap)
			hq.heappush(minheap, toMin)
			hq.heappush(maxheap, -1 * toMax)
		x = -1 * maxheap[0]
		print(float(x))
	else:
		toMin = -1 * hq.heappushpop(maxheap, -1 * x)
		hq.heappush(minheap, toMin)
		x = (-1 * maxheap[0] + minheap[0]) / 2.0
		print(x)


import heapq

class solution:

	def inputList(self, nums):
		if len(nums) < 1:
			return []
		lower = [-nums[0]]
		upper = []
		out = [float(nums[0])]
		for i in range(1, len(nums)):
			if i % 2 == 0:
				d1 = nums[i]
				d2 = heapq.heappop(upper)
				heapq.heappush(lower, -min(d1, d2))
				heapq.heappush(upper, max(d1, d2))
				out.append(round(float(-lower[0]), 1))
			else:
				d1 = nums[i]
				d2 = -heapq.heappop(lower)
				heapq.heappush(upper, max(d1, d2))
				heapq.heappush(lower, -min(d1, d2))
				out.append(round((-lower[0] + upper[0]) / 2, 1))
		return out
n = int(input())
nums = []
for i in range(n):
	nums.append(int(input()))
sol = solution()
result = sol.inputList(nums)
for item in result:
	print(item)


import bisect

def median(nums):
	if len(nums) % 2 == 0:
		return (nums[len(nums) // 2 - 1] + nums[len(nums) // 2]) / 2
	else:
		return nums[len(nums) // 2]
t = int(input())
nums = []
for _ in range(t):
	if nums == []:
		nums.append(int(input()))
		print(float(nums[0]))
		continue
	n = int(input())
	numLen = len(nums)
	bisect.insort(nums, n)
	print(float(median(nums)))


from abc import ABCMeta, abstractmethod

class Heap:
	__metaclass__ = ABCMeta

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

	@abstractmethod
	def insert(self, e):
		pass

	def top(self):
		return self.items[0]

	def parent(self, i):
		return i // 2

	def left(self, i):
		return i * 2

	def right(self, i):
		return i * 2 + 1

	def size(self):
		return len(self.items)

	def extract(self):
		v = self.items[0]
		self.items[0] = self.items[-1]
		self.items.pop()
		self.heapify(0)
		return v

	@abstractmethod
	def heapify(self, i):
		pass

class MinHeap(Heap):

	def insert(self, e):
		self.items.append(e)
		i = self.size() - 1
		while i > 0 and self.items[self.parent(i)] >= self.items[i]:
			(self.items[i], self.items[self.parent(i)]) = (self.items[self.parent(i)], self.items[i])
			i = self.parent(i)

	def heapify(self, i):
		(l, r) = (self.left(i), self.right(i))
		if l < self.size() and self.items[i] > self.items[l]:
			smallest = l
		else:
			smallest = i
		if r < self.size() and self.items[smallest] > self.items[r]:
			smallest = r
		if smallest != i:
			(self.items[i], self.items[smallest]) = (self.items[smallest], self.items[i])
			self.heapify(smallest)

class MaxHeap(Heap):

	def insert(self, e):
		self.items.append(e)
		i = self.size() - 1
		while i > 0 and self.items[self.parent(i)] <= self.items[i]:
			(self.items[i], self.items[self.parent(i)]) = (self.items[self.parent(i)], self.items[i])
			i = self.parent(i)

	def heapify(self, i):
		(l, r) = (self.left(i), self.right(i))
		if l < self.size() and self.items[i] < self.items[l]:
			largest = l
		else:
			largest = i
		if r < self.size() and self.items[largest] < self.items[r]:
			largest = r
		if largest != i:
			(self.items[i], self.items[largest]) = (self.items[largest], self.items[i])
			self.heapify(largest)
maxheap = MaxHeap()
minheap = MinHeap()
n = int(input())
median = int(input())
print(float(median))
maxheap.insert(median)
for i in range(1, n):
	num = int(input())
	if num > median:
		minheap.insert(num)
	else:
		maxheap.insert(num)
	if maxheap.size() > minheap.size() + 1:
		v = maxheap.extract()
		minheap.insert(v)
	if minheap.size() > maxheap.size() + 1:
		v = minheap.extract()
		maxheap.insert(v)
	if i % 2 == 1:
		median = (maxheap.top() + minheap.top()) / 2
	elif minheap.size() > maxheap.size():
		median = minheap.top()
	else:
		median = maxheap.top()
	print(float(median))


import heapq
N = int(input())
top_heap = []
bottom_heap = []
oneoff = False
for n in range(N):
	a = int(input())
	if len(top_heap) == 0:
		heapq.heappush(top_heap, a)
		oneoff = True
	elif a >= top_heap[0]:
		if oneoff:
			b = heapq.heappushpop(top_heap, a)
			heapq.heappush(bottom_heap, -b)
			oneoff = False
		else:
			heapq.heappush(top_heap, a)
			oneoff = True
	elif not oneoff:
		b = heapq.heappushpop(bottom_heap, -a)
		heapq.heappush(top_heap, -b)
		oneoff = True
	else:
		heapq.heappush(bottom_heap, -a)
		oneoff = False
	if oneoff:
		print(top_heap[0])
	else:
		print((top_heap[0] - bottom_heap[0]) / 2)


count = int(input())

def rough_bin_search(l, val):
	mid = start = 0
	end = len(l)
	while start < end:
		mid = (start + end) // 2
		if l[mid] == val:
			break
		elif start == mid:
			if val > l[mid]:
				mid = mid + 1
			break
		elif l[mid] < val:
			start = mid
		else:
			end = mid
	return mid
l = []
while count > 0:
	count -= 1
	val = int(input())
	l.insert(rough_bin_search(l, val), val)
	if len(l) % 2 == 1:
		print('{:.1f}'.format(l[len(l) // 2]))
	else:
		lowmid = l[len(l) // 2 - 1]
		upmid = l[len(l) // 2]
		median = (lowmid + upmid) / 2.0
		print('{:.1f}'.format(median))


from bisect import bisect
import sys
n_integ = int(sys.stdin.readline())
input_iter = map(int, sys.stdin.read().split('\n')[:-1])
malen = 0
maliste = []
for new_input in input_iter:
	maliste.insert(bisect(maliste, new_input), new_input)
	malen += 1
	if malen % 2 == 0:
		print(sum(maliste[int(malen / 2 - 1):int(malen / 2 + 1)]) / 2)
	else:
		print(maliste[int((malen - 1) / 2)])


from heapq import *

def heapify_max(heap):
	for i in range(len(heap)):
		heap[i] = -heap[i]
	heapify(heap)

def heappush_max(heap, item):
	heappush(heap, -item)

def heappop_max(heap):
	return -heappop(heap)

def heappeek(heap):
	x = heappop(heap)
	heappush(heap, x)
	return x

def heappeek_max(heap):
	x = heappop_max(heap)
	heappush_max(heap, x)
	return x
n = int(input())
median = 0
left_max_heap = []
right_min_heap = []
for i in range(n):
	x = int(input())
	if x <= median:
		heappush_max(left_max_heap, x)
	else:
		heappush(right_min_heap, x)
	left = len(left_max_heap)
	right = len(right_min_heap)
	if left - right > 1:
		heappush(right_min_heap, heappop_max(left_max_heap))
	elif right - left > 1:
		heappush_max(left_max_heap, heappop(right_min_heap))
	left = len(left_max_heap)
	right = len(right_min_heap)
	if left == right:
		median = (heappeek_max(left_max_heap) + heappeek(right_min_heap)) / 2
	elif left > right:
		median = heappeek_max(left_max_heap)
	else:
		median = heappeek(right_min_heap)
	print(median)


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


import heapq
t = int(input())
(maxh, minh) = ([], [])
(a, b) = (int(input()), int(input()))
print(a / 1)
if a > b:
	heapq.heappush(minh, a)
	heapq.heappush(maxh, -b)
else:
	heapq.heappush(maxh, -a)
	heapq.heappush(minh, b)
print((-maxh[0] + minh[0]) / 2)
for i in range(t - 2):
	item = int(input())
	if item > minh[0]:
		heapq.heappush(minh, item)
	else:
		heapq.heappush(maxh, -item)
	diff = len(maxh) - len(minh)
	if diff > 1:
		for j in range(diff // 2):
			heapq.heappush(minh, -heapq.heappop(maxh))
	elif diff < 1:
		for j in range(-diff // 2):
			heapq.heappush(maxh, -heapq.heappop(minh))
	if diff % 2 == 0:
		print((-maxh[0] + minh[0]) / 2)
	elif diff > 0:
		print(-maxh[0])
	else:
		print(minh[0])


import bisect
num_nums = int(input().strip())
data = []
for _ in range(num_nums):
	number = int(input().strip())
	data.insert(bisect.bisect(data, number), number)
	if len(data) % 2 == 0:
		print((data[len(data) // 2 - 1] + data[len(data) // 2]) / 2)
	else:
		print(data[len(data) // 2])


from heapq import heappush, heappop
heap_lower = []
heap_upper = []
N = int(input())
for i in range(0, N):
	k = int(input())
	if heap_upper and heap_upper[0] < k:
		heappush(heap_upper, k)
	else:
		heappush(heap_lower, -k)
	while len(heap_lower) > len(heap_upper) + 1:
		heappush(heap_upper, -heappop(heap_lower))
	while len(heap_lower) + 1 < len(heap_upper):
		heappush(heap_lower, -heappop(heap_upper))
	if len(heap_upper) > len(heap_lower):
		print(float(heap_upper[0]))
	elif len(heap_upper) < len(heap_lower):
		print(-float(heap_lower[0]))
	else:
		print((-heap_lower[0] + heap_upper[0]) / 2.0)


import heapq
(lower, upper, median) = ([], [], None)
N = int(input())
for i in range(N):
	if median == None:
		median = int(input())
		print(median)
	else:
		next_number = int(input())
		if i % 2 == 1:
			if next_number > median:
				heapq.heappush(upper, next_number)
				print((upper[0] + median) / 2)
			else:
				heapq.heappush(lower, -next_number)
				print((-lower[0] + median) / 2)
		else:
			if len(lower) > len(upper):
				if next_number > median:
					heapq.heappush(upper, next_number)
				else:
					heapq.heappush(upper, median)
					heapq.heappush(lower, -next_number)
					median = -heapq.heappop(lower)
			elif next_number < median:
				heapq.heappush(lower, -next_number)
			else:
				heapq.heappush(lower, -median)
				heapq.heappush(upper, next_number)
				median = heapq.heappop(upper)
			print(median)


import heapq

class MinHeap:

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

	def extract_min(self):
		return heapq.heappop(self._heap)

	def find_min(self):
		return self._heap[0]

	def insert(self, n):
		heapq.heappush(self._heap, n)

class MaxHeap:

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

	def insert(self, n):
		heapq.heappush(self._heap, -n)

	def extract_max(self):
		return -heapq.heappop(self._heap)

	def find_max(self):
		return -self._heap[0]
N = int(input())
min_heap = MinHeap()
max_heap = MaxHeap()
for i in range(N):
	a = int(input())
	if i == 0:
		max_heap.insert(a)
		print(float(a))
	elif i == 1:
		b = max_heap.find_max()
		if b < a:
			min_heap.insert(a)
		else:
			b = max_heap.extract_max()
			max_heap.insert(a)
			min_heap.insert(b)
		print((a + b) / 2)
	elif i % 2 == 0:
		left = max_heap.find_max()
		right = min_heap.find_min()
		if a > right:
			right = min_heap.extract_min()
			min_heap.insert(a)
			max_heap.insert(right)
		else:
			max_heap.insert(a)
		left = max_heap.find_max()
		print(float(left))
	else:
		left = max_heap.find_max()
		right = min_heap.find_min()
		if a < left:
			left = max_heap.extract_max()
			max_heap.insert(a)
			min_heap.insert(left)
		else:
			min_heap.insert(a)
		left = max_heap.find_max()
		right = min_heap.find_min()
		print((left + right) / 2)


import bisect
import sys
from math import floor
array = []
for line in sys.stdin.readlines()[1:]:
	n = int(line.strip())
	bisect.insort_right(array, n)
	if len(array) == 1:
		print('%.1f' % array[0])
	elif len(array) % 2 == 0:
		idx = floor(len(array) / 2) - 1
		print('%.1f' % ((array[idx] + array[idx + 1]) / 2))
	else:
		print('%.1f' % array[len(array) // 2])


from bisect import insort
size = int(input())
lst = []

def median(sortedLst):
	lstLen = len(lst)
	index = (lstLen - 1) // 2
	if lstLen % 2:
		return sortedLst[index] * 1.0
	else:
		return (sortedLst[index] + sortedLst[index + 1]) / 2.0
for i in range(size):
	nr = int(input())
	insort(lst, nr)
	print(median(lst))


import heapq
l = int(input())
(n1, n2) = (int(input()), int(input()))
if n1 > n2:
	(minheap, maxheap) = ([n1], [-1 * n2])
else:
	(minheap, maxheap) = ([n2], [-1 * n1])
print(n1)
print((n1 + n2) / 2)
for _ in range(l - 2):
	n = int(input())
	if n < -1 * maxheap[0]:
		heapq.heappush(maxheap, -1 * n)
	else:
		heapq.heappush(minheap, n)
	if abs(len(maxheap) - len(minheap)) >= 2:
		if len(maxheap) > len(minheap):
			heapq.heappush(minheap, abs(heapq.heappop(maxheap)))
		else:
			heapq.heappush(maxheap, -1 * heapq.heappop(minheap))
	if len(minheap) == len(maxheap):
		print(sum(map(abs, [minheap[0], maxheap[0]])) / 2)
	else:
		print(abs(maxheap[0]) if len(maxheap) > len(minheap) else minheap[0])


import sys
import bisect
n = int(sys.stdin.readline())
a = []
for i in range(0, n):
	new = int(sys.stdin.readline())
	bisect.insort(a, new)
	if len(a) % 2 == 0:
		index1 = int(len(a) / 2) - 1
		index2 = int(len(a) / 2 + 1) - 1
		print((a[index1] + a[index2]) / 2)
	else:
		index = int((len(a) + 1) / 2) - 1
		print(a[index])


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


from heapq import *
under = []
upper = []
N = int(input())
for _ in range(N):
	curNumber = int(input())
	if len(upper) == 0:
		upper.append(curNumber)
		print(curNumber)
		continue
	middle = upper[0]
	if curNumber >= middle:
		heappush(upper, curNumber)
	else:
		heappush(under, -curNumber)
	if len(under) >= len(upper):
		heappush(upper, -heappop(under))
	if len(upper) >= len(under) + 2:
		heappush(under, -heappop(upper))
	if (len(upper) + len(under)) % 2 == 1:
		print(float(upper[0]))
	else:
		print((float(upper[0]) + -under[0]) / 2)


from math import floor, log
import heapq

def log2(x):
	return log(x) / log(2)

class Heap(object):

	def __init__(self, max_=False, col=[]):
		self.max_heap = max_
		self.array = list(col)
		self.Heapify()

	def Add(self, val):
		heapq.heappush(self.array, val)

	def Heapify(self):
		heapq.heapify(self.array)

	def last_index(self):
		return len(self.array) - 1

	def get_top(self):
		if self.Size() > 0:
			return self.array[0]
		else:
			return None

	def HeapPushPop(self, val):
		return heapq.heappushpop(self.array, val)

	def HeapReplace(self, val):
		return heapq.heapreplace(self.array, val)

	def extract_top(self):
		return heapq.heappop(self.array)

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

	def __repr__(self):
		return str(self)

	def Size(self):
		return len(self.array)

	def __getitem__(self, key):
		return self.array[key]

	def __setitem__(self, key, val):
		self.array[key] = val

class MaxHeap(Heap):

	def __init__(self, col=[]):
		colinv = [-x for x in col]
		Heap.__init__(self, True, colinv)

	def Add(self, val):
		Heap.Add(self, -val)

	def extract_top(self):
		val = Heap.extract_top(self)
		return -val

	def __getitem__(self, key):
		return -self.array[key]

	def __setitem__(self, key, val):
		self.array[key] = -val

	def get_top(self):
		val = Heap.get_top(self)
		return -val if val else None

	def HeapReplace(self, val):
		return -Heap.HeapReplace(self, -val)

	def HeapPushPop(self, val):
		return -Heap.HeapPushPop(self, -val)

class MinHeap(Heap):

	def __init__(self, col=[]):
		Heap.__init__(self, False, col)

def GetMedian(heap1, heap2):
	sz1 = heap1.Size()
	sz2 = heap2.Size()
	if sz2 == sz1:
		res = (heap2.get_top() + heap1.get_top()) / 2
	else:
		res = heap1.get_top() if sz1 > sz2 else heap2.get_top()
	return float(res)

def AddNumberToHeaps(over, under, n):
	sz_over = over.Size()
	sz_under = under.Size()
	if sz_under > sz_over:
		top_under = under.get_top() or -1
		if n < top_under:
			tmp = under.HeapReplace(n)
			over.Add(tmp)
		else:
			over.Add(n)
	else:
		top_over = over.get_top() or 100000000000.0
		if n > top_over:
			tmp = over.HeapReplace(n)
			under.Add(tmp)
		else:
			under.Add(n)

def ProcessMedian(lst):
	under = MaxHeap()
	over = MinHeap()
	res = []
	for n in lst:
		AddNumberToHeaps(over, under, n)
		res.append(GetMedian(under, over))
	return res

def GetValuesFromConsole():
	T = int(input())
	nums = []
	for it in range(T):
		nums.append(int(input()))
	return nums
nums = GetValuesFromConsole()
res = ProcessMedian(nums)
for val in res:
	print(val)


from math import *

class Heap:

	def __init__(self, nature):
		self.__tracker_array = []
		self.__nature = nature

	def insert(self, key):
		self.__tracker_array.append(key)
		self.bubble_up(len(self.__tracker_array) - 1)

	def extract(self):
		temp = self.getter(0)
		self.__tracker_array[0] = self.getter(-1)
		self.__tracker_array.pop()
		self.bubble_down(0)
		return temp

	def peek(self):
		return self.__tracker_array[0]

	def size(self):
		return len(self.__tracker_array)

	def bubble_up(self, pos):
		while self.parent(pos) >= 0:
			parent_val = self.getter(self.parent(pos))
			current_val = self.getter(pos)
			if self.__nature == 'min' and current_val >= parent_val or (self.__nature == 'max' and current_val <= parent_val):
				return None
			else:
				self.swap(self.parent(pos), pos)
				pos = self.parent(pos)
		return None

	def bubble_down(self, pos):
		while 2 * pos + 1 < len(self.__tracker_array):
			next_pos = self.get_next_pos(pos)
			if next_pos == pos:
				break
			else:
				self.swap(next_pos, pos)
				pos = next_pos
		return None

	def swap(self, p1, p2):
		temp = self.getter(p1)
		self.__tracker_array[p1] = self.getter(p2)
		self.__tracker_array[p2] = temp

	def get_next_pos(self, pos):
		extremum = self.getter(pos)
		extremum_pos = pos
		left = self.left(pos)
		right = self.right(pos)
		if self.more_extreme(extremum, left):
			extremum = self.getter(left)
			extremum_pos = left
		if self.more_extreme(extremum, right):
			extremum = self.getter(right)
			extremum_pos = right
		return extremum_pos

	def more_extreme(self, value, pos):
		if self.__nature == 'min' and self.getter(pos) is not None and (self.getter(pos) <= value) or (self.__nature == 'max' and self.getter(pos) is not None and (self.getter(pos) >= value)):
			return True
		else:
			return False

	@staticmethod
	def parent(pos):
		return floor((pos - 1) / 2)

	@staticmethod
	def left(pos):
		return pos * 2 + 1

	@staticmethod
	def right(pos):
		return pos * 2 + 2

	def getter(self, pos):
		if pos >= len(self.__tracker_array):
			return None
		else:
			return self.__tracker_array[pos]

class MedianHeap:

	def __init__(self):
		self.__min_heap = Heap('min')
		self.__max_heap = Heap('max')
		self.__median = 0

	def insert(self, value):
		if value >= self.__median:
			self.__min_heap.insert(value)
		else:
			self.__max_heap.insert(value)
		self.rebalance()
		size_min_heap = self.__min_heap.size()
		size_max_heap = self.__max_heap.size()
		if size_min_heap > size_max_heap:
			self.__median = self.__min_heap.peek()
		elif size_max_heap > size_min_heap:
			self.__median = self.__max_heap.peek()
		else:
			self.__median = (self.__min_heap.peek() + self.__max_heap.peek()) / 2

	def peek(self):
		return self.__median

	def rebalance(self):
		size_min_heap = self.__min_heap.size()
		size_max_heap = self.__max_heap.size()
		if size_min_heap - size_max_heap > 1:
			value = self.__min_heap.extract()
			self.__max_heap.insert(value)
		elif size_max_heap - size_min_heap > 1:
			value = self.__max_heap.extract()
			self.__min_heap.insert(value)
		return None
num_entries = int(input())
median_heap = MedianHeap()
for i in range(num_entries):
	next_entry = int(input())
	median_heap.insert(next_entry)
	print(median_heap.peek())


import bisect

def median(midlist):
	lens = len(midlist)
	if lens % 2 != 0:
		midl = int(lens / 2)
		res = midlist[midl]
	else:
		odd = int(lens / 2) - 1
		ev = int(lens / 2)
		res = float(midlist[odd] + midlist[ev]) / float(2)
	return res
tc = int(input())
ar = []
while tc > 0:
	tc -= 1
	bisect.insort(ar, int(input()))
	print(float(median(ar)))


import heapq

class MedianIntegerStream:

	def __init__(self):
		self.min_heap = list()
		self.max_heap = list()
		self.total_numbers = 0

	def insert(self, number):
		if self.total_numbers % 2 != 0:
			num_for_min_heap = -1 * heapq.heappushpop(self.max_heap, -1 * number)
			heapq.heappush(self.min_heap, num_for_min_heap)
			self.total_numbers += 1
			return
		heapq.heappush(self.max_heap, -1 * number)
		self.total_numbers += 1
		if len(self.min_heap) == 0:
			return
		if -1 * self.max_heap[0] <= self.min_heap[0]:
			return
		num_for_min_heap = -1 * heapq.heappop(self.max_heap)
		num_for_max_heap = heapq.heappop(self.min_heap)
		heapq.heappush(self.max_heap, -1 * num_for_max_heap)
		heapq.heappush(self.min_heap, num_for_min_heap)

	def get_median(self):
		if self.total_numbers % 2 != 0:
			return -1 * self.max_heap[0]
		return (-1 * self.max_heap[0] + self.min_heap[0]) / 2
stream = MedianIntegerStream()
for _ in range(int(input())):
	stream.insert(int(input()))
	print('%.1f' % stream.get_median())


num = int(input())
lst = []

def binary_search(lst, number):
	first = 0
	last = len(lst) - 1
	midpoint = 0
	while first <= last:
		midpoint = (first + last) // 2
		if lst[midpoint] == number:
			return midpoint
		elif number < lst[midpoint]:
			last = midpoint - 1
		else:
			first = midpoint + 1
	if first > last:
		return first
	else:
		return last

def find_median(lst):
	length = len(lst)
	if length % 2 == 0:
		return lst[length // 2] / 2 + lst[length // 2 - 1] / 2
	else:
		return lst[length // 2]
for i in range(num):
	number = int(input())
	lst.insert(binary_search(lst, number), number)
	print(float(find_median(lst)))


from heapq import heappush, heappushpop
n = int(input())
lo = []
hi = []
for i in range(n):
	a = int(input())
	if lo and a > -lo[0]:
		if len(hi) > len(lo):
			heappush(lo, -heappushpop(hi, a))
			m = (hi[0] - lo[0]) / 2
		else:
			heappush(hi, a)
			if len(hi) > len(lo):
				m = hi[0]
			else:
				m = (hi[0] - lo[0]) / 2
	elif len(lo) > len(hi):
		heappush(hi, -heappushpop(lo, -a))
		m = (hi[0] - lo[0]) / 2
	else:
		heappush(lo, -a)
		if len(lo) > len(hi):
			m = -lo[0]
		else:
			m = (hi[0] - lo[0]) / 2
	print('{:.1f}'.format(m))


import sys, heapq
n = int(sys.stdin.readline())
lines = sys.stdin.readlines()
minHeap = []
maxHeap = []
median = 0
for line in lines:
	element = int(line.strip())
	if element > median:
		heapq.heappush(minHeap, element)
	else:
		heapq.heappush(maxHeap, element * -1)
	if len(minHeap) - len(maxHeap) > 1:
		heapq.heappush(maxHeap, heapq.heappop(minHeap) * -1)
	elif len(maxHeap) - len(minHeap) > 1:
		heapq.heappush(minHeap, heapq.heappop(maxHeap) * -1)
	if len(minHeap) > len(maxHeap):
		median = minHeap[0]
	elif len(minHeap) < len(maxHeap):
		median = maxHeap[0] * -1
	else:
		median = (minHeap[0] + maxHeap[0] * -1) / 2
	print(float(median))


from heapq import heappush, heappushpop

def printn(n):
	print('{:.01f}'.format(n))
N = int(input())
for i in range(min(N, 2)):
	a = int(input())
	if i == 0:
		printn(a)
		max_heap = [-a]
	else:
		printn((a + -max_heap[0]) / 2)
		if a >= -max_heap[0]:
			min_heap = [a]
		else:
			min_heap = [-max_heap[0]]
			max_heap = [-a]
for i in range(2, N):
	a = int(input())
	if i % 2:
		if len(max_heap) < (i + 1) // 2:
			if a <= -max_heap[0]:
				heappush(max_heap, -a)
			else:
				a = heappushpop(min_heap, a)
				heappush(max_heap, -a)
		elif a >= min_heap[0]:
			heappush(min_heap, a)
		else:
			a = -heappushpop(max_heap, -a)
			heappush(min_heap, a)
		printn((min_heap[0] + -max_heap[0]) / 2)
	elif a <= -max_heap[0]:
		heappush(max_heap, -a)
		printn(-max_heap[0])
	else:
		heappush(min_heap, a)
		printn(min_heap[0])


from heapq import *
N = int(input())
lower = []
upper = []
midlow = midup = 0
for i in range(N):
	val = float(input())
	if val >= midup:
		heappush(upper, val)
		midup = val
	else:
		heappush(lower, -val)
		midlow = val
	if len(upper) > len(lower) + 1:
		heappush(lower, -heappop(upper))
	if len(lower) > len(upper) + 1:
		heappush(upper, -heappop(lower))
	if lower:
		midlow = -lower[0]
	if upper:
		midup = upper[0]
	if len(lower) == len(upper):
		print((midlow + midup) / 2.0)
	elif len(lower) > len(upper):
		print(midlow)
	else:
		print(midup)


import heapq

class MinHeap(object):

	def __init__(self, array=None):
		if not array:
			array = []
		self.array = array
		heapq.heapify(array)

	def push(self, item):
		heapq.heappush(self.array, item)

	def pop(self):
		return heapq.heappop(self.array)

	def peek(self):
		return self.array[0]

	def __bool__(self):
		return bool(self.array)

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

class MaxHeap(object):

	def __init__(self, array=None):
		if not array:
			array = []
		for (i, entry) in enumerate(array):
			array[i] = -entry
		self.array = array
		heapq.heapify(array)

	def push(self, item):
		heapq.heappush(self.array, -item)

	def pop(self):
		return -heapq.heappop(self.array)

	def peek(self):
		return -self.array[0]

	def __bool__(self):
		return bool(self.array)

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

class MedianTracker(list):

	def __init__(self):
		self.low = MaxHeap()
		self.high = MinHeap()
		self.mid = None

	def median(self):
		if self.mid is None:
			return (self.low.peek() + self.high.peek()) / 2
		return self.mid

	def push(self, entry):
		displaced = entry
		if self.low and entry < self.low.peek():
			displaced = self.low.pop()
			self.low.push(entry)
		elif self.high and entry > self.high.peek():
			displaced = self.high.pop()
			self.high.push(entry)
		if self.mid is None:
			self.mid = displaced
		else:
			(low, high) = (min(self.mid, displaced), max(self.mid, displaced))
			self.low.push(low)
			self.high.push(high)
			self.mid = None

	def pop(self, entry):
		if self.mid is None:
			return (self.low.pop() + self.high.pop()) / 2
		mid = self.mid
		self.mid = None
		return mid
tracker = MedianTracker()
N = int(input())
for _ in range(N):
	tracker.push(int(input()))
	print(tracker.median())


import bisect
col = []
for i in range(int(input())):
	bisect.insort_left(col, int(input()))
	mid = len(col) // 2
	values = col[mid - i % 2:mid + 1]
	print(sum(values) / len(values))


import heapq
from random import shuffle
maxh = []
minh = []
for _ in range(int(input())):
	i = int(input())
	if len(maxh) == len(minh):
		if len(minh) and minh[0] < i:
			heapq.heappush(maxh, -heapq.heappop(minh))
			heapq.heappush(minh, i)
		else:
			heapq.heappush(maxh, -i)
	elif -maxh[0] > i:
		heapq.heappush(minh, -heapq.heappop(maxh))
		heapq.heappush(maxh, -i)
	else:
		heapq.heappush(minh, i)
	print(-maxh[0] if len(maxh) > len(minh) else (-maxh[0] + minh[0]) / 2)


from heapq import *

def balance(A, B):
	while len(A) > len(B):
		a = -heappop(A)
		heappush(B, a)
	while len(B) - len(A) > 1:
		a = heappop(B)
		heappush(A, -a)

def getMedian(A, B):
	if len(B) > len(A):
		return B[0]
	else:
		return (-A[0] + B[0]) / 2.0

def insert(A, B, a):
	if A and a < -A[0]:
		heappush(A, -a)
	else:
		heappush(B, a)
	balance(A, B)
A = []
B = []
N = int(input().strip())
for _ in range(N):
	a = int(input().strip())
	insert(A, B, a)
	m = getMedian(A, B)
	print(m)


import heapq

class MaxHeap:

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

	def push(self, value):
		heapq.heappush(self.heap, -value)

	def pop(self):
		return -heapq.heappop(self.heap)

	def top(self):
		return -self.heap[0]
n = int(input())
min_h = []
max_h = MaxHeap()
arr = []
first_elements = 2
elements = 0
for _ in range(n):
	el = int(input())
	elements += 1
	if first_elements:
		arr.append(el)
		print(arr[len(arr) // 2] if len(arr) % 2 == 1 else (arr[len(arr) // 2 - 1] + arr[len(arr) // 2]) / 2)
		first_elements -= 1
		if first_elements == 0:
			arr.sort()
			max_h.push(arr[0])
			heapq.heappush(min_h, arr[1])
			first_elements = False
	else:
		if el < max_h.top():
			max_h.push(el)
		else:
			heapq.heappush(min_h, el)
		if len(min_h) > len(max_h.heap):
			max_h.push(heapq.heappop(min_h))
		elif len(max_h.heap) > len(min_h):
			heapq.heappush(min_h, max_h.pop())
		if elements % 2 == 1:
			if len(min_h) > len(max_h.heap):
				print(min_h[0])
			else:
				print(max_h.top())
		else:
			print((min_h[0] + max_h.top()) / 2)


from bisect import insort
from math import floor, ceil
lst = []
for i in range(int(input().strip())):
	insort(lst, int(input().strip()))
	m = (lst[floor(i / 2)] + lst[ceil(i / 2)]) / 2
	print('%.1f' % m)


import heapq
n = int(input().strip())
num_list = []
less = []
more = []
equal = []
for i in range(n):
	num = int(input().strip())
	if i == 0:
		median = num
		num_list.append(num)
	elif i < 3:
		num_list.append(num)
		num_list.sort()
		if len(num_list) % 2 == 0:
			index = len(num_list) // 2 - 1
			median = (num_list[index] + num_list[index + 1]) / 2
		else:
			index = len(num_list) // 2
			median = num_list[index]
		if i == 2:
			less.append(-1 * num_list[1])
			less.append(-1 * num_list[0])
			more.append(num_list[2])
			heapq.heapify(less)
			heapq.heapify(more)
			nodes = 3
	elif nodes % 2 == 0:
		heapq.heappush(less, -1 * num)
		if less[0] * -1 > more[0]:
			temp = heapq.heappop(less) * -1
			heapq.heappush(less, -1 * heapq.heappop(more))
			heapq.heappush(more, temp)
		nodes += 1
		median = -1 * less[0]
	else:
		heapq.heappush(more, num)
		if less[0] * -1 > more[0]:
			temp = heapq.heappop(less) * -1
			heapq.heappush(less, -1 * heapq.heappop(more))
			heapq.heappush(more, temp)
		nodes += 1
		median = (-1 * less[0] + more[0]) / 2
	print('{0:.1f}'.format(median))


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


import heapq
maxx = []
minx = []

def get_median(x):
	if len(minx) > 0 and x < minx[0] and (len(minx) >= len(maxx)) or (len(maxx) > 0 and x < -maxx[0]):
		if len(maxx) > len(minx):
			max_v = -heapq.heappop(maxx)
			heapq.heappush(minx, max_v)
		heapq.heappush(maxx, -x)
	else:
		if len(minx) > len(maxx):
			min_v = heapq.heappop(minx)
			heapq.heappush(maxx, -min_v)
		heapq.heappush(minx, x)
	if len(maxx) > len(minx):
		return float(-maxx[0])
	elif len(minx) > len(maxx):
		return float(minx[0])
	else:
		return float((minx[0] - maxx[0]) / 2)

def local():
	with open('../../tests/find-median/1.txt') as f:
		n = int(f.readline())
		while n > 0:
			num = int(f.readline())
			res = get_median(int(num))
			print('{:.1f}'.format(res))
			n -= 1

def server():
	n = int(input())
	while n > 0:
		num = input()
		res = get_median(int(num))
		print('{:.1f}'.format(res))
		n -= 1
server()


import heapq
heapmax = []
heapmin = []
median = -1
N = int(input())
for n in range(N):
	a = int(input())
	if a > median:
		heapq.heappush(heapmin, a)
	else:
		heapq.heappush(heapmax, -a)
	if abs(len(heapmax) - len(heapmin)) > 1:
		if len(heapmax) > len(heapmin):
			maxx = -heapq.heappop(heapmax)
			heapq.heappush(heapmin, maxx)
		else:
			minn = heapq.heappop(heapmin)
			heapq.heappush(heapmax, -minn)
	if len(heapmax) == len(heapmin):
		median = (heapmin[0] - heapmax[0]) / 2
	elif len(heapmax) > len(heapmin):
		median = -heapmax[0]
	else:
		median = heapmin[0]
	print(median)


num = int(input().strip())
import heapq
smaller = []
bigger = []
j = 0
for run in range(num):
	i = int(input().strip())
	if j == 0:
		smaller.append(-1 * i)
		heapq.heapify(smaller)
		j += 1
	elif -1 * i < smaller[0]:
		if len(bigger) == 0:
			bigger.append(i)
			heapq.heapify(bigger)
		else:
			heapq.heappush(bigger, i)
	else:
		heapq.heappush(smaller, -1 * i)
	if len(bigger) - len(smaller) > 1:
		trans = heapq.heappop(bigger)
		heapq.heappush(smaller, -1 * trans)
	elif len(smaller) - len(bigger) > 1:
		trans = heapq.heappop(smaller)
		heapq.heappush(bigger, -1 * trans)
	if len(bigger) == len(smaller):
		med = (-1 * smaller[0] + bigger[0]) / 2
	elif len(bigger) - len(smaller) == 1:
		med = bigger[0]
	elif len(smaller) - len(bigger) == 1:
		med = -1 * smaller[0]
	print('{:.1f}'.format(med))


import heapq
less = []
more = []

def med():
	if not less and (not more):
		return 9e+99
	if len(less) > len(more):
		return -less[0]
	return (more[0] - less[0]) / 2
for i in range(int(input())):
	x = float(input())
	if x < med():
		heapq.heappush(less, -x)
	else:
		heapq.heappush(more, x)
	while more and -less[0] > more[0] or len(less) > len(more) + 1:
		heapq.heappush(more, -heapq.heappop(less))
	while len(more) > len(less):
		heapq.heappush(less, -heapq.heappop(more))
	print(med())


import heapq

class OnlineMedian(object):

	def __init__(self):
		self.small = []
		self.large = []

	def add(self, elm):
		if len(self.small) + len(self.large) == 0:
			self.small.append(-elm)
		elif elm > self.median():
			heapq.heappush(self.large, elm)
		else:
			heapq.heappush(self.small, -elm)
		self.balance()

	def balance(self):
		if len(self.small) > len(self.large) + 1:
			move = heapq.heappop(self.small)
			heapq.heappush(self.large, -move)
		elif len(self.large) > len(self.small) + 1:
			move = heapq.heappop(self.large)
			heapq.heappush(self.small, -move)

	def median(self):
		med = None
		if not len(self.small):
			med = self.large[0]
		elif not len(self.large):
			med = -self.small[0]
		elif len(self.small) > len(self.large):
			med = -self.small[0]
		elif len(self.large) > len(self.small):
			med = self.large[0]
		else:
			med = (self.large[0] - self.small[0]) / 2
		return float(med)

def main():
	size = int(input(''))
	med = OnlineMedian()
	for _ in range(size):
		med.add(int(input('')))
		print('%.1f' % med.median())
main()


import math, heapq
minH = []
maxH = []
median = [10 ** 6]
for _ in range(int(input())):
	temp = float(input())
	if temp >= median[-1]:
		heapq.heappush(minH, temp)
	else:
		heapq.heappush(maxH, -temp)
	lenMin = len(minH)
	lenMax = len(maxH)
	if lenMin - lenMax == 2:
		heapq.heappush(maxH, -heapq.heappop(minH))
		lenMin -= 1
		lenMax += 1
	elif lenMax - lenMin == 2:
		heapq.heappush(minH, abs(heapq.heappop(maxH)))
		lenMin += 1
		lenMax -= 1
	if lenMin == lenMax:
		median.append((abs(maxH[0]) + minH[0]) / 2)
	elif lenMin > lenMax:
		median.append(minH[0])
	else:
		median.append(abs(maxH[0]))
print('\n'.join([str(x) for x in median[1:]]))


import heapq

def median(min_heap, max_heap):
	if len(min_heap) == len(max_heap):
		return (min_heap[0] - max_heap[0]) / 2
	else:
		return -max_heap[0]
N = int(input())
min_heap = []
max_heap = []
for i in range(N):
	a = int(input())
	if min_heap and a > min_heap[0]:
		heapq.heappush(min_heap, a)
		if len(min_heap) > len(max_heap):
			heapq.heappush(max_heap, -heapq.heappop(min_heap))
	else:
		heapq.heappush(max_heap, -a)
		if len(max_heap) > len(min_heap) + 1:
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
	print('{0:0.1f}'.format(median(min_heap, max_heap)))


import heapq

def median(min_heap, max_heap):
	if len(min_heap) == len(max_heap):
		return (min_heap[0] - max_heap[0]) / 2
	else:
		return -max_heap[0]
N = int(input())
min_heap = []
max_heap = []
for i in range(N):
	a = int(input())
	if min_heap and a > min_heap[0]:
		heapq.heappush(min_heap, a)
		if len(min_heap) > len(max_heap):
			heapq.heappush(max_heap, -heapq.heappop(min_heap))
	else:
		heapq.heappush(max_heap, -a)
		if len(max_heap) > len(min_heap) + 1:
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
	print('{0:0.1f}'.format(median(min_heap, max_heap)))


class MinHeap:

	def __init__(self):
		self.heap = [None]

	def insert(self, data):
		self.heap.append(data)
		self.sift_up(len(self.heap) - 1)

	def min(self):
		if len(self.heap) >= 2:
			return self.heap[1]
		else:
			return None

	def delete_min(self):
		if len(self.heap) > 1:
			last_el = self.heap[len(self.heap) - 1]
			self.heap[len(self.heap) - 1] = self.heap[1]
			self.heap[1] = last_el
			ret_val = self.heap.pop()
			self.sift_down(1)
		return ret_val

	def delete(self, val):
		i = self.heap.index(val)
		self.heap[i] = self.heap[len(self.heap) - 1]
		self.heap.pop()
		if i != len(self.heap):
			if i > 1 and self.heap[i] < self.heap[self.parent(i)]:
				self.sift_up(i)
			else:
				self.sift_down(i)

	def parent(self, k):
		if int(k / 2) > 0:
			return int(k / 2)

	def left_child(self, k):
		if len(self.heap) > 2 * k:
			return 2 * k

	def right_child(self, k):
		if len(self.heap) > 2 * k + 1:
			return 2 * k + 1

	def sift_up(self, ind):
		cur_pos = ind
		data = self.heap[cur_pos]
		cur_parent = self.parent(cur_pos)
		while cur_pos > 1 and data < self.heap[cur_parent]:
			self.heap[cur_pos] = self.heap[cur_parent]
			cur_pos = cur_parent
			cur_parent = self.parent(cur_pos)
		self.heap[cur_pos] = data

	def sift_down(self, ind):
		cur_pos = ind
		l = self.left_child(cur_pos)
		r = self.right_child(cur_pos)
		while l or r:
			if l:
				l_val = self.heap[l]
			if r:
				r_val = self.heap[r]
			if l and r:
				if l_val < r_val:
					self.heap[l] = self.heap[cur_pos]
					self.heap[cur_pos] = l_val
					cur_pos = l
				else:
					self.heap[r] = self.heap[cur_pos]
					self.heap[cur_pos] = r_val
					cur_pos = r
			elif l:
				self.heap[l] = self.heap[cur_pos]
				self.heap[cur_pos] = l_val
				cur_pos = l
			else:
				self.heap[r] = self.heap[cur_pos]
				self.heap[cur_pos] = r_val
				cur_pos = r
			l = self.left_child(cur_pos)
			r = self.right_child(cur_pos)

class MaxHeap:

	def __init__(self):
		self.heap = [None]

	def insert(self, data):
		self.heap.append(data)
		self.sift_up(len(self.heap) - 1)

	def max(self):
		if len(self.heap) >= 2:
			return self.heap[1]
		else:
			return None

	def delete_max(self):
		if len(self.heap) > 1:
			last_el = self.heap[len(self.heap) - 1]
			self.heap[len(self.heap) - 1] = self.heap[1]
			self.heap[1] = last_el
			ret_val = self.heap.pop()
			self.sift_down(1)
		return ret_val

	def delete(self, val):
		i = self.heap.index(val)
		self.heap[i] = self.heap[len(self.heap) - 1]
		self.heap.pop()
		if i != len(self.heap):
			if i > 1 and self.heap[i] > self.heap[self.parent(i)]:
				self.sift_up(i)
			else:
				self.sift_down(i)

	def parent(self, k):
		if int(k / 2) > 0:
			return int(k / 2)

	def left_child(self, k):
		if len(self.heap) > 2 * k:
			return 2 * k

	def right_child(self, k):
		if len(self.heap) > 2 * k + 1:
			return 2 * k + 1

	def sift_up(self, ind):
		cur_pos = ind
		data = self.heap[cur_pos]
		cur_parent = self.parent(cur_pos)
		while cur_pos > 1 and data > self.heap[cur_parent]:
			self.heap[cur_pos] = self.heap[cur_parent]
			cur_pos = cur_parent
			cur_parent = self.parent(cur_pos)
		self.heap[cur_pos] = data

	def sift_down(self, ind):
		cur_pos = ind
		if cur_pos > 1:
			cur_val = self.heap[cur_pos]
		l = self.left_child(cur_pos)
		r = self.right_child(cur_pos)
		while l or r:
			cur_val = self.heap[cur_pos]
			if l:
				l_val = self.heap[l]
			if r:
				r_val = self.heap[r]
			if l and r:
				if l_val > r_val and cur_val < l_val:
					self.heap[l] = self.heap[cur_pos]
					self.heap[cur_pos] = l_val
					cur_pos = l
				elif cur_val < r_val:
					self.heap[r] = self.heap[cur_pos]
					self.heap[cur_pos] = r_val
					cur_pos = r
				else:
					break
			elif l and cur_val < l_val:
				self.heap[l] = self.heap[cur_pos]
				self.heap[cur_pos] = l_val
				cur_pos = l
			elif r and cur_val < r_val:
				self.heap[r] = self.heap[cur_pos]
				self.heap[cur_pos] = r_val
				cur_pos = r
			else:
				break
			l = self.left_child(cur_pos)
			r = self.right_child(cur_pos)

class Median:

	def __init__(self):
		self.med = None
		self.min_heap = MinHeap()
		self.max_heap = MaxHeap()
		self.data = 0

	def insert(self, data):
		if self.data == 0:
			self.med = data
		min_length = len(self.min_heap.heap)
		max_length = len(self.max_heap.heap)
		if min_length == max_length:
			if data > self.med:
				self.min_heap.insert(data)
			else:
				self.max_heap.insert(data)
		elif min_length < max_length:
			if data > self.med:
				self.min_heap.insert(data)
			else:
				cur_max = self.max_heap.delete_max()
				self.min_heap.insert(cur_max)
				self.max_heap.insert(data)
		elif data < self.med:
			self.max_heap.insert(data)
		else:
			cur_min = self.min_heap.delete_min()
			self.max_heap.insert(cur_min)
			self.min_heap.insert(data)
		self.get_median()
		self.data += 1

	def get_median(self):
		min_length = len(self.min_heap.heap)
		max_length = len(self.max_heap.heap)
		cur_min = self.min_heap.min()
		cur_max = self.max_heap.max()
		if cur_min == 0 or cur_min is None:
			cur_min = cur_max
		if cur_max == 0 or cur_max is None:
			cur_max = cur_min
		if min_length == max_length:
			self.med = (cur_min + cur_max) / 2
		elif min_length > max_length:
			self.med = cur_min
		else:
			self.med = cur_max
		print(round(self.med, 1))
m = Median()
n = int(input().strip())
for i in range(n):
	m.insert(int(input().strip()))


import bisect
N = int(input())
x = int(input())
print('%.1f' % x)
a = [x]
for i in range(2, N + 1):
	x = int(input())
	bisect.insort(a, x)
	if i % 2 == 0:
		median = (a[i // 2 - 1] + a[i // 2]) / 2.0
	else:
		median = float(a[i // 2])
	print('%.1f' % median)


import heapq

def median(min_heap, max_heap):
	if len(min_heap) == len(max_heap):
		return (min_heap[0] - max_heap[0]) / 2
	else:
		return -max_heap[0]
N = int(input())
min_heap = []
max_heap = []
for i in range(N):
	a = int(input())
	if min_heap and a > min_heap[0]:
		heapq.heappush(min_heap, a)
		if len(min_heap) > len(max_heap):
			heapq.heappush(max_heap, -heapq.heappop(min_heap))
	else:
		heapq.heappush(max_heap, -a)
		if len(max_heap) > len(min_heap) + 1:
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
	print('{0:0.1f}'.format(median(min_heap, max_heap)))


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []
		self.size = 0

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.size += 1
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


class heap:

	def __init__(self):
		self.arr = []
		self.size = 0

	def get_top(self):
		if self.size > 0:
			return self.arr[0]

	def left_child(self, i):
		return 2 * i + 1

	def right_child(self, i):
		return 2 * i + 2

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

	def bubble_up(self, i):
		curr = i
		while curr > 0:
			par = self.parent(curr)
			if self.arr[curr] < self.arr[par]:
				(self.arr[curr], self.arr[par]) = (self.arr[par], self.arr[curr])
				curr = par
			else:
				break

	def bubble_down(self, i):
		curr = i
		while self.left_child(curr) < self.size:
			if self.right_child(curr) >= self.size or self.arr[self.left_child(curr)] <= self.arr[self.right_child(curr)]:
				chil = self.left_child(curr)
			else:
				chil = self.right_child(curr)
			if self.arr[curr] > self.arr[chil]:
				(self.arr[curr], self.arr[chil]) = (self.arr[chil], self.arr[curr])
				curr = chil
			else:
				break

	def add(self, v):
		self.arr.append(v)
		self.bubble_up(self.size)
		self.size += 1

	def delete(self, v):
		i = self.arr.index(v)
		if i == self.size - 1:
			self.arr.pop()
			self.size -= 1
			return
		self.arr[i] = self.arr.pop()
		self.size -= 1
		self.bubble_up(i)
		self.bubble_down(i)
minh = heap()
maxh = heap()
for _ in range(int(input())):
	v = int(input())
	if maxh.size == 0 or v <= -maxh.get_top():
		maxh.add(-v)
	else:
		minh.add(v)
	while abs(maxh.size - minh.size) > 1:
		if maxh.size > minh.size:
			top = -maxh.get_top()
			minh.add(top)
			maxh.delete(-top)
		else:
			top = minh.get_top()
			maxh.add(-top)
			minh.delete(top)
	if maxh.size == minh.size:
		print((minh.get_top() - maxh.get_top()) / 2)
	elif maxh.size == minh.size + 1:
		print(float(-maxh.get_top()))
	else:
		print(float(minh.get_top()))


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


import heapq
N = int(input())
if N == 1:
	print('{:.1f}'.format(int(input())))
elif N == 2:
	print('{:.1f}'.format((int(input()) + int(input())) / 2.0))
else:
	maxh = []
	minh = []
	(x, y) = (int(input()), int(input()))
	if x < y:
		heapq.heappush(maxh, -x)
		heapq.heappush(minh, y)
	else:
		heapq.heappush(maxh, -y)
		heapq.heappush(minh, x)
	print('{:.1f}'.format(x))
	print('{:.1f}'.format((x + y) / 2.0))
	for i in range(2, N):
		z = int(input())
		if i % 2 == 0:
			if z <= minh[0]:
				heapq.heappush(maxh, -z)
			else:
				aux = heapq.heapreplace(minh, z)
				heapq.heappush(maxh, -aux)
			print('{:.1f}'.format(float(-maxh[0])))
		else:
			if z > -maxh[0]:
				heapq.heappush(minh, z)
			else:
				aux = heapq.heapreplace(maxh, -z)
				heapq.heappush(minh, -aux)
			print('{:.1f}'.format((-maxh[0] + minh[0]) / 2.0))


class Heap:

	def __init__(self, ismin=True):
		self.arr = []
		self.m = ismin

	def swap(self, i, j):
		temp = self.arr[i]
		self.arr[i] = self.arr[j]
		self.arr[j] = temp

	def heapifyUp(self, i):
		if i == 0:
			return
		if self.m:
			if self.arr[i] < self.arr[i // 2]:
				self.swap(i, i // 2)
				self.heapifyUp(i // 2)
		elif self.arr[i] > self.arr[i // 2]:
			self.swap(i, i // 2)
			self.heapifyUp(i // 2)

	def heapifyDown(self, i):
		if self.m:
			if i * 2 < len(self.arr):
				j = i * 2
				m = self.arr[j]
				if j + 1 < len(self.arr) and m > self.arr[j + 1]:
					j = j + 1
					m = self.arr[j]
				if m < self.arr[i]:
					self.swap(i, j)
					self.heapifyDown(j)
		elif i * 2 < len(self.arr):
			j = i * 2
			m = self.arr[j]
			if j + 1 < len(self.arr) and m < self.arr[j + 1]:
				j = j + 1
				m = self.arr[j]
			if m > self.arr[i]:
				self.swap(i, j)
				self.heapifyDown(j)

	def add(self, v):
		self.arr.append(v)
		self.heapifyUp(len(self.arr) - 1)

	def root(self):
		return self.arr[0]

	def len(self):
		return len(self.arr)

	def remove(self, v):
		k = len(self.arr) - 1
		i = self.arr.index(v)
		self.swap(i, k)
		del self.arr[k]
		self.heapifyDown(i)
n = int(input().strip())
r = Heap()
l = Heap(ismin=False)
i = 0
while i < n:
	if i % 2 == 0:
		l.add(int(input().strip()))
		if r.len() > 0 and r.root() < l.root():
			t = r.root()
			r.remove(t)
			r.add(l.root())
			l.remove(l.root())
			l.add(t)
		print('%.1f' % (l.root() / 1.0))
	else:
		r.add(int(input().strip()))
		if r.root() < l.root():
			t = r.root()
			r.remove(t)
			r.add(l.root())
			l.remove(l.root())
			l.add(t)
		print('%.1f' % ((l.root() + r.root()) / 2.0))
	i += 1


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


def min_heapify(A, i):
	l = i * 2 + 1
	r = i * 2 + 2
	n = len(A)
	i_sm = i
	if l < n and A[l] < A[i]:
		i_sm = l
	if r < n and A[r] < A[i_sm]:
		i_sm = r
	if i != i_sm:
		(A[i], A[i_sm]) = (A[i_sm], A[i])
		min_heapify(A, i_sm)

def max_heapify(A, i):
	l = i * 2 + 1
	r = i * 2 + 2
	n = len(A)
	i_lg = i
	if l < n and A[l] > A[i]:
		i_lg = l
	if r < n and A[r] > A[i_lg]:
		i_lg = r
	if i != i_lg:
		(A[i], A[i_lg]) = (A[i_lg], A[i])
		max_heapify(A, i_lg)

def min_bubble_up(A, i):
	p = (i - 1) // 2
	if p >= 0 and A[i] < A[p]:
		(A[p], A[i]) = (A[i], A[p])
		min_bubble_up(A, p)

def max_bubble_up(A, i):
	p = (i - 1) // 2
	if p >= 0 and A[i] > A[p]:
		(A[p], A[i]) = (A[i], A[p])
		max_bubble_up(A, p)

def extract_max(A):
	n = len(A)
	i_n = n - 1
	if n < 1:
		raise ValueError('Heap underflow')
	elif n == 1:
		return A.pop(0)
	elif n > 1:
		m = A[0]
		A[0] = A.pop(i_n)
		max_heapify(A, 0)
		return m

def extract_min(A):
	n = len(A)
	i_n = n - 1
	if n < 1:
		raise ValueError('Heap underflow')
	elif n == 1:
		return A.pop(0)
	elif n > 1:
		m = A[0]
		A[0] = A.pop(i_n)
		min_heapify(A, 0)
		return m

def min_insert(A, z):
	A.append(z)
	n = len(A)
	if n > 1:
		i_n = n - 1
		min_bubble_up(A, i_n)

def max_insert(A, z):
	A.append(z)
	n = len(A)
	if n > 1:
		i_n = n - 1
		max_bubble_up(A, i_n)

def get_median(A, B):
	l_a = len(A)
	l_b = len(B)
	if l_a == 0 and l_b == 0:
		return 0
	if l_a == l_b:
		return abs(A[0] + B[0]) / 2.0
	elif l_a > l_b:
		return A[0]
	elif l_b > l_a:
		return B[0]

def rebalance(MAX, MIN):
	l_max = len(MAX)
	l_min = len(MIN)
	if abs(l_max - l_min) > 1:
		if l_max > l_min:
			z = extract_max(MAX)
			min_insert(MIN, z)
		elif l_min > l_max:
			z = extract_min(MIN)
			max_insert(MAX, z)

def update(z, MAX, MIN):
	if len(MAX) == 0 and len(MIN) == 0 or z < MAX[0]:
		max_insert(MAX, z)
	else:
		min_insert(MIN, z)
	if abs(len(MAX) - len(MIN)) > 1:
		rebalance(MAX, MIN)
hmax = []
hmin = []
q = int(input())
for i in range(0, q):
	try:
		x = int(input())
	except Exception as e:
		pass
	update(x, hmax, hmin)
	print('{:3.1f}'.format(get_median(hmax, hmin)))


import heapq as hq

class MedianTracker:

	def __init__(self):
		self.fh = []
		self.sh = []

	def insert(self, elt):
		if not self.fh or elt < -self.fh[0]:
			hq.heappush(self.fh, -elt)
		else:
			hq.heappush(self.sh, elt)
		self.rebalance()

	def rebalance(self):
		(lf, ls) = (len(self.fh), len(self.sh))
		if lf > ls + 1:
			elt = -hq.heappop(self.fh)
			hq.heappush(self.sh, elt)
		elif ls > lf + 1:
			elt = hq.heappop(self.sh)
			hq.heappush(self.fh, -elt)

	def median(self):
		(lf, ls) = (len(self.fh), len(self.sh))
		if lf > ls:
			return -self.fh[0]
		elif ls > lf:
			return self.sh[0]
		else:
			return (self.sh[0] - self.fh[0]) / 2
N = int(input().strip())
tracker = MedianTracker()
for i in range(N):
	k = int(input().strip())
	tracker.insert(k)
	ret = tracker.median()
	print(round(ret, 1))


import sys
import math
import heapq

class MidHeap:

	def __init__(self):
		self.minH = []
		self.minS = 0
		self.maxH = []
		self.maxS = 0

	def median(self):
		if self.minS == 0 and self.maxS == 0:
			return 0
		if self.minS > self.maxS:
			med = self.minH[0]
		elif self.maxS > self.minS:
			med = self.maxH[0] * -1
		else:
			med = (float(self.minH[0]) + self.maxH[0] * -1) / 2
		return float(med)

	def insert(self, x):
		if x > self.median():
			heapq.heappush(self.minH, x)
			self.minS = self.minS + 1
		else:
			heapq.heappush(self.maxH, x * -1)
			self.maxS = self.maxS + 1
		if self.minS - self.maxS > 1:
			heapq.heappush(self.maxH, heapq.heappop(self.minH) * -1)
			self.minS = self.minS - 1
			self.maxS = self.maxS + 1
		elif self.maxS - self.minS > 1:
			heapq.heappush(self.minH, heapq.heappop(self.maxH) * -1)
			self.minS = self.minS + 1
			self.maxS = self.maxS - 1

	def printHeaps(self):
		print('MinH: ', self.minH)
		print('MaxH: ', self.maxH)
t = int(input().strip())
midH = MidHeap()
for a0 in range(t):
	x = int(input().strip())
	midH.insert(x)
	print(midH.median())


class SortedList:

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

	def insert(self, value):
		if len(self.list) == 0:
			self.list.append(value)
		elif self.list[0] > value:
			self.list.insert(0, value)
		elif self.list[-1] < value:
			self.list.append(value)
		else:
			front = 0
			end = len(self.list) - 1
			while True:
				mid = (front + end) // 2
				if self.list[mid] < value:
					if front == mid:
						self.list.insert(mid + 1, value)
						return
					else:
						front = mid
				elif self.list[mid] > value:
					end = mid
				elif self.list[mid] == value:
					self.list.insert(mid, value)
					return

	def get_median(self):
		if len(self.list) % 2 == 0:
			return (self.list[len(self.list) // 2] + self.list[len(self.list) // 2 - 1]) / 2
		else:
			return self.list[len(self.list) // 2]
n = int(input())
a = SortedList()
for i in range(n):
	a.insert(int(input()))
	print('{:.1f}'.format(a.get_median()))


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


import sys
import heapq

class Median(object):

	def __init__(self):
		self.min = []
		self.max = []

	def add(self, num):
		if len(self.max) > len(self.min):
			if num >= -self.max[0]:
				heapq.heappush(self.min, num)
			else:
				heapq.heappush(self.min, -heapq.heappop(self.max))
				heapq.heappush(self.max, -num)
		elif len(self.min) > 0 and num >= self.min[0]:
			heapq.heappush(self.max, -heapq.heappop(self.min))
			heapq.heappush(self.min, num)
		else:
			heapq.heappush(self.max, -num)

	def median(self):
		if len(self.max) == len(self.min):
			return (-self.max[0] + self.min[0]) / 2
		else:
			return -self.max[0]

def main():
	N = int(sys.stdin.readline())
	m = Median()
	while N > 0:
		i = int(sys.stdin.readline())
		m.add(i)
		print(m.median())
		N = N - 1
main()


import heapq

class MedianTracker:

	def __init__(self):
		self.first_half = []
		self.second_half = []

	def insert(self, item):
		if self.first_half == [] or item < -self.first_half[0]:
			heapq.heappush(self.first_half, -item)
		else:
			heapq.heappush(self.second_half, item)
		self.rebalance()

	def rebalance(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len - second_len > 1:
			elt = -heapq.heappop(self.first_half)
			heapq.heappush(self.second_half, elt)
		elif second_len - first_len > 1:
			elt = -heapq.heappop(self.second_half)
			heapq.heappush(self.first_half, elt)

	def median(self):
		first_len = len(self.first_half)
		second_len = len(self.second_half)
		if first_len > second_len:
			result = -self.first_half[0]
		elif second_len > first_len:
			result = self.second_half[0]
		else:
			result = (-self.first_half[0] + self.second_half[0]) / 2
		return '{:.1f}'.format(result)
t = int(input())
mt = MedianTracker()
for _ in range(t):
	mt.insert(int(input()))
	print(mt.median())


from heapq import heappush, heappop
N = int(input())
min_heap = []
max_heap = []
for i in range(N):
	num = int(input())
	if i == 0:
		heappush(max_heap, -num)
		print('{0:.1f}'.format(float(num)))
		continue
	elif num <= -max_heap[0]:
		heappush(max_heap, -num)
	else:
		heappush(min_heap, num)
	if len(max_heap) < len(min_heap) - 1:
		heappush(max_heap, -heappop(min_heap))
	elif len(min_heap) < len(max_heap) - 1:
		heappush(min_heap, -heappop(max_heap))
	current_median = float(0)
	if len(min_heap) == len(max_heap):
		current_median = (float(-max_heap[0]) + float(min_heap[0])) / float(2)
	elif len(min_heap) > len(max_heap):
		current_median = float(min_heap[0])
	else:
		current_median = float(-max_heap[0])
	print('{0:.1f}'.format(current_median))


import heapq
N = int(input())
maxheap = []
minheap = []

def get_median():
	lmin = len(minheap)
	lmax = len(maxheap)
	if lmax > lmin:
		return float(-maxheap[0])
	elif lmin > lmax:
		return float(minheap[0])
	else:
		return float((minheap[0] - maxheap[0]) / 2)
for _ in range(N):
	v = int(input())
	if not minheap:
		heapq.heappush(minheap, v)
	elif v < minheap[0]:
		heapq.heappush(maxheap, -v)
	elif v > minheap[0]:
		heapq.heappush(minheap, v)
	else:
		heapq.heappush(minheap, v)
	lmin = len(minheap)
	lmax = len(maxheap)
	if lmin - 1 > lmax:
		heapq.heappush(maxheap, -heapq.heappop(minheap))
	elif lmax - 1 > lmin:
		heapq.heappush(minheap, -heapq.heappop(maxheap))
	print('{:.1f}'.format(get_median()))


class Heap(object):
	MAX_HEAP = 1
	MIN_HEAP = 2

	def __init__(self, heap_type=MIN_HEAP):
		self.__heap = []
		if heap_type == self.MIN_HEAP:
			self.__comparator = lambda x, y: x < y
		else:
			self.__comparator = lambda x, y: x > y

	def sift_up(self, i):
		j = (i - 1) // 2
		while i > 0 and j >= 0 and self.__comparator(self.__heap[i], self.__heap[j]):
			(self.__heap[i], self.__heap[j]) = (self.__heap[j], self.__heap[i])
			i = j
			j = (i - 1) // 2

	def sift_down(self, i):
		while i < len(self.__heap):
			j = 2 * i + 1
			if 2 * i + 2 < len(self.__heap) and self.__comparator(self.__heap[2 * i + 2], self.__heap[2 * i + 1]):
				j += 1
			if j < len(self.__heap) and self.__comparator(self.__heap[j], self.__heap[i]):
				(self.__heap[i], self.__heap[j]) = (self.__heap[j], self.__heap[i])
				i = j
			else:
				break

	def add(self, x):
		self.__heap.append(x)
		self.sift_up(len(self.__heap) - 1)

	def rem(self, x):
		i = self.__heap.index(x)
		if i == len(self.__heap) - 1:
			self.__heap.pop()
			return
		else:
			self.__heap[i] = self.__heap.pop()
		if i == 0:
			self.sift_down(i)
		elif self.__comparator(self.__heap[i], self.__heap[(i - 1) // 2]):
			self.sift_up(i)
		else:
			self.sift_down(i)

	def top(self):
		return self.__heap[0] if len(self.__heap) > 0 else None

	def size(self):
		return len(self.__heap)

	def __repr__(self):
		return '|' + ','.join((str(x) for x in self.__heap)) + '|'

class MedianFinder(object):

	def __init__(self):
		self._max_heap = Heap(Heap.MAX_HEAP)
		self._min_heap = Heap(Heap.MIN_HEAP)
		self.cur_median = None

	def add_number(self, num):
		if self._max_heap.size() == self._min_heap.size() == 0 and self.cur_median is None:
			self.cur_median = num
		else:
			median = self.get_median()
			if num < median:
				if self.cur_median is not None:
					self._min_heap.add(self.cur_median)
					self._max_heap.add(num)
					self.cur_median = None
				else:
					max_elem = self._max_heap.top()
					if num <= max_elem:
						self._max_heap.rem(max_elem)
						self._max_heap.add(num)
						self.cur_median = max_elem
					else:
						self.cur_median = num
			elif self.cur_median is not None:
				self._max_heap.add(self.cur_median)
				self._min_heap.add(num)
				self.cur_median = None
			else:
				min_elem = self._min_heap.top()
				if num >= min_elem:
					self._min_heap.rem(min_elem)
					self._min_heap.add(num)
					self.cur_median = min_elem
				else:
					self.cur_median = num

	def get_median(self):
		if self.cur_median is not None:
			return self.cur_median
		else:
			if self._max_heap.size() == 0 and self._min_heap.size() == 0:
				return None
			return (self._max_heap.top() + self._min_heap.top()) / 2 if self.cur_median is None else self.cur_median

	def __repr__(self):
		out = 'L{} {} R{}'.format(self._max_heap, self.cur_median, self._min_heap)
		return out
Q = int(input().strip())
median_finder = MedianFinder()
for q in range(Q):
	v = int(input().strip())
	median_finder.add_number(v)
	print('{0:.1f}'.format(median_finder.get_median()))


import heapq
left = []
right = []

def output(n):
	print('{0:.1f}'.format(n))
for t in range(int(input())):
	n = int(input())
	if not left or -left[0] >= n:
		heapq.heappush(left, -n)
	else:
		heapq.heappush(right, n)
	if len(left) > len(right) + 1:
		heapq.heappush(right, -heapq.heappop(left))
	elif len(right) > len(left) + 1:
		heapq.heappush(left, -heapq.heappop(right))
	if len(left) == len(right):
		output((-left[0] + right[0]) / 2)
	elif len(left) < len(right):
		output(right[0])
	else:
		output(-left[0])


import math

def heapPush(heap, value):
	current = len(heap)
	heap.append(value)
	parent = int(math.floor((current - 1) / 2))
	while parent >= 0:
		if heap[current] < heap[parent]:
			temp = heap[parent]
			heap[parent] = heap[current]
			heap[current] = temp
			current = parent
			parent = int(math.floor((current - 1) / 2))
		else:
			break

def heapPop(heap):
	if not heap:
		return None
	head = heap[0]
	end = heap.pop()
	heap[0] = end
	siftDown(heap, 0)
	return head

def siftDown(heap, start):

	def leftChild(heap, i):
		chIndex = 2 * int(i) + 1
		if len(heap) >= chIndex + 1:
			return chIndex
		else:
			return None

	def rightChild(heap, i):
		chIndex = 2 * int(i) + 2
		if len(heap) >= chIndex + 1:
			return chIndex
		else:
			return None
	current = start
	while leftChild(heap, current) != None:
		lChild = leftChild(heap, current)
		rChild = rightChild(heap, current)
		swap = current
		if heap[lChild] < heap[swap]:
			swap = lChild
		if rChild and heap[rChild] < heap[swap]:
			swap = rChild
		if swap == current:
			return
		else:
			temp = heap[current]
			heap[current] = heap[swap]
			heap[swap] = temp
			current = swap

def main():
	heapA = []
	heapB = []
	N = int(input())
	for i in range(N):
		new = int(input())
		if not heapA or new < abs(heapA[0]):
			neg = -1 * new
			heapPush(heapA, neg)
		else:
			heapPush(heapB, new)
		diff = abs(len(heapA) - len(heapB))
		if len(heapA) > len(heapB):
			if diff > 1:
				switch = -1 * heapPop(heapA)
				heapPush(heapB, switch)
				val1 = -1.0 * heapA[0]
				val2 = 1.0 * heapB[0]
				median = (val1 + val2) / 2.0
			else:
				median = -1.0 * heapA[0]
		elif len(heapA) < len(heapB):
			if diff > 1:
				switch = -1 * heapPop(heapB)
				heapPush(heapA, switch)
				val1 = -1.0 * heapA[0]
				val2 = 1.0 * heapB[0]
				median = (val1 + val2) / 2.0
			else:
				median = heapB[0] / 1.0
		else:
			val1 = -1.0 * heapA[0]
			val2 = 1.0 * heapB[0]
			median = (val1 + val2) / 2.0
		print(median)
main()


N = int(input().strip())
median = None
lt = [0 for dummy in range(N)]
gt = [0 for dummy in range(N)]

def okay(a, b, heapType):
	if heapType == 'max':
		return a >= b
	else:
		return a <= b

def replaceRoot(heap, newVal, heapSize, heapType):
	heap[0] = newVal
	curr = 0
	leftInd = 1
	rightInd = 2
	while leftInd < heapSize:
		leftOkay = okay(heap[curr], heap[leftInd], heapType)
		rightOkay = rightInd >= heapSize or okay(heap[curr], heap[rightInd], heapType)
		if leftOkay and rightOkay:
			break
		if leftOkay and (not rightOkay):
			indToSwap = rightInd
		elif rightOkay and (not leftOkay):
			indToSwap = leftInd
		elif heapType == 'max':
			indToSwap = leftInd if heap[leftInd] > heap[rightInd] else rightInd
		else:
			indToSwap = rightInd if heap[leftInd] > heap[rightInd] else leftInd
		temp = heap[curr]
		heap[curr] = heap[indToSwap]
		heap[indToSwap] = temp
		curr = indToSwap
		leftInd = 2 * curr + 1
		rightInd = 2 * curr + 2

def heapSize(N_i):
	if N_i % 2 == 0:
		return int(N_i / 2)
	else:
		return int((N_i - 1) / 2)

def getParent(ind):
	if ind % 2 == 0:
		return int((ind - 2) / 2)
	else:
		return int((ind - 1) / 2)

def heapAdd(heap, newVal, heapSize, heapType):
	heap[heapSize] = newVal
	curr = heapSize
	while curr > 0 and (not okay(heap[getParent(curr)], heap[curr], heapType)):
		temp = heap[curr]
		heap[curr] = heap[getParent(curr)]
		heap[getParent(curr)] = temp
		curr = getParent(curr)
for N_i in range(N):
	val = int(input().strip())
	if median == None:
		if N_i == 0:
			median = val
		elif val >= lt[0] and val <= gt[0]:
			median = val
		elif val < lt[0]:
			median = lt[0]
			replaceRoot(lt, val, heapSize(N_i), 'max')
		else:
			median = gt[0]
			replaceRoot(gt, val, heapSize(N_i), 'min')
	else:
		if val <= median:
			heapAdd(lt, val, heapSize(N_i), 'max')
			heapAdd(gt, median, heapSize(N_i), 'min')
		else:
			heapAdd(lt, median, heapSize(N_i), 'max')
			heapAdd(gt, val, heapSize(N_i), 'min')
		median = None
	if median != None:
		print('%0.1f' % median)
	else:
		print('%0.1f' % ((lt[0] + gt[0]) / 2))


class Heap:

	def __init__(self, size, mult):
		self.data = [int()] * size
		self.index = 0
		self.multiplier = mult

	def add(self, value):
		value *= self.multiplier
		self.data[self.index] = value
		pos = self.index
		self.index += 1
		while pos > 0 and value < self.data[int(pos / 2)]:
			self.data[pos] = self.data[int(pos / 2)]
			pos = int(pos / 2)
		self.data[pos] = value

	def remove(self, value):
		index = self.data.index(value)

	def pop(self):
		value = self.data[0]
		self.index -= 1
		swapVal = self.data[self.index]
		self.data[0] = swapVal
		self.reheap(0)
		self.data[self.index] = 0
		return value

	def reheap(self, index):
		left = 2 * index
		right = 2 * index + 1
		smallest = index
		if left < self.index and self.data[left] < self.data[smallest]:
			smallest = left
		if right < self.index and self.data[right] < self.data[smallest]:
			smallest = right
		if smallest != index:
			temp = self.data[index]
			self.data[index] = self.data[smallest]
			self.data[smallest] = temp
			self.reheap(smallest)

class Median:

	def __init__(self, size):
		self.minHeap = Heap(size, 1)
		self.maxHeap = Heap(size, -1)
		self.size = size
		self.count = 0

	def insert(self, val):
		self.count += 1
		if self.minHeap.index == 0 or self.minHeap.data[0] < val:
			self.minHeap.add(val)
		else:
			self.maxHeap.add(val)
		self.rebalance()

	def rebalance(self):
		if self.maxHeap.index > self.minHeap.index:
			while self.maxHeap.index > self.minHeap.index:
				self.minHeap.add(self.maxHeap.pop() * -1)
		elif self.minHeap.index > self.maxHeap.index:
			while self.minHeap.index > self.maxHeap.index:
				self.maxHeap.add(self.minHeap.pop())
		if self.maxHeap.data[0] * -1 > self.minHeap.data[0] and self.maxHeap.index > 0 and (self.minHeap.index > 0):
			temp1 = self.maxHeap.pop() * -1
			temp2 = self.minHeap.pop()
			self.maxHeap.add(temp2)
			self.minHeap.add(temp1)

	def print(self):
		if self.count % 2 != 0:
			if self.maxHeap.index > self.minHeap.index:
				print(float(self.maxHeap.data[0] * -1))
			else:
				print(float(self.minHeap.data[0]))
		else:
			print((self.maxHeap.data[0] * -1 + self.minHeap.data[0]) / 2)
x = int(input())
medianTrack = Median(x)
for i in range(x):
	num = int(input())
	medianTrack.insert(num)
	medianTrack.print()


import heapq
(L, H) = ([], [])
for _ in range(int(input())):
	a = int(input())
	if not H:
		heapq.heappush(H, a)
	elif len(H) > len(L):
		if H[0] < a:
			b = heapq.heappushpop(H, a)
			heapq.heappush(L, -b)
		else:
			heapq.heappush(L, -a)
	elif -L[0] > a:
		b = -heapq.heappushpop(L, -a)
		heapq.heappush(H, b)
	else:
		heapq.heappush(H, a)
	if len(H) > len(L):
		print('%.1f' % H[0])
	else:
		print('%.1f' % ((H[0] - L[0]) / 2))


import sys
import bisect

class sortlist:

	def __init__(self, list):
		self.list = list
		self.sort()

	def sort(self):
		(l, i) = ([], 0)
		for i in range(len(self.list)):
			bisect.insort(l, self.list[i])
		self.list = l
		self.len = i

	def insert(self, value):
		bisect.insort(self.list, value)
		self.len += 1

	def search(self, value):
		left = bisect.bisect_left(self.list, value)
		if abs(self.list[min([left, self.len - 1])] - value) >= abs(self.list[left - 1] - value):
			return self.list[left - 1]
		else:
			return self.list[left]
n = int(input().strip())
a = sortlist([])
a_i = 0
for a_i in range(n):
	a_t = int(input().strip())
	a.insert(a_t)
	if a_i == 0:
		print(float(a_t))
	elif a_i == 1:
		print((a.list[0] + a.list[1]) / 2)
	elif a_i % 2:
		print(float((a.list[a_i // 2] + a.list[a_i // 2 + 1]) / 2))
	else:
		print(float(a.list[a_i // 2]))


from bisect import insort
n = int(input())
lst = []
even = False
for i in range(n):
	insort(lst, int(input()))
	if even:
		print(0.5 * (lst[i // 2] + lst[i // 2 + 1]))
		even = False
	else:
		print(1.0 * lst[i // 2])
		even = True


from heapq import *
iterations = int(input())
low = []
high = []
for i in range(iterations):
	number = float(input())
	if len(low) == 0:
		low.append(-1 * number)
	elif len(high) == 0:
		heappush(low, -1 * number)
		high.append(-1 * heappop(low))
	elif number > high[0]:
		heappush(high, number)
	elif number <= high[0]:
		heappush(low, -1 * number)
	diff = abs(len(low) - len(high))
	if diff == 2:
		if len(low) > len(high):
			removed = -1 * heappop(low)
			heappush(high, removed)
		else:
			removed = -1 * heappop(high)
			heappush(low, removed)
		diff = 0
	if diff == 0:
		print((abs(low[0]) + high[0]) / 2)
	elif diff == 1:
		if len(low) > len(high):
			print(-1 * low[0])
		else:
			print(high[0])


import heapq

class MedianTracker:

	def __init__(self):
		self.lower_half = []
		self.upper_half = []

	def insert(self, element):
		if len(self.lower_half) == len(self.upper_half):
			heapq.heappush(self.lower_half, -heapq.heappushpop(self.upper_half, -element))
		else:
			heapq.heappush(self.upper_half, -heapq.heappushpop(self.lower_half, element))

	def median(self):
		if len(self.lower_half) == len(self.upper_half):
			return (self.lower_half[0] - self.upper_half[0]) / 2.0
		else:
			return self.lower_half[0]
n = int(input())
median = MedianTracker()
for i in range(n):
	element = int(input())
	median.insert(element)
	print('{0:.1f}'.format(median.median()))


import heapq as q
N = int(input().strip())
maxl = []
minl = []

def getMedian(maxl, minl):
	lenMin = len(minl)
	lenMax = len(maxl)
	totalLen = lenMax + lenMin
	if totalLen % 2 == 0 and totalLen != 0:
		a = maxl[0]
		b = -minl[0]
		return (a + b) / 2
	elif lenMin > lenMax:
		return -minl[0]
	else:
		return maxl[0]

def rebalance2(maxl, minl):
	while len(maxl) > len(minl):
		a = q.heappop(maxl)
		q.heappush(minl, -a)
	while len(minl) > len(maxl):
		a = q.heappop(minl)
		q.heappush(maxl, -a)
m = -1
for _ in range(N):
	a = int(input().strip())
	if a > m:
		q.heappush(maxl, a)
	else:
		q.heappush(minl, -a)
	rebalance2(maxl, minl)
	m = getMedian(maxl, minl)
	print(float(m))


class Heap:

	def __init__(self, hType='MIN'):
		self.d = [None]
		if hType == 'MIN':
			self.compare = lambda x, y: x <= y
		else:
			self.compare = lambda x, y: y <= x

	def add(self, v):
		self.d.append(v)
		index = len(self.d) - 1
		while index >= 1:
			parent = index // 2
			if parent <= 0:
				break
			if self.compare(self.d[index], self.d[parent]):
				(self.d[index], self.d[parent]) = (self.d[parent], self.d[index])
				index = parent
			else:
				break

	def size(self):
		return len(self.d) - 1

	def top(self):
		if self.size() <= 0:
			return None
		return self.d[1]

	def pop(self):
		if self.size() <= 0:
			return None
		top = self.d[1]
		last = self.d.pop()
		if self.size() > 0:
			self.d[1] = last
			index = 1
			while index:
				(c1, c2) = (index * 2, index * 2 + 1)
				mc = None
				if c1 >= 1 and c1 < len(self.d):
					if c2 <= 0 or c2 >= len(self.d):
						mc = c1
					elif self.compare(self.d[c1], self.d[c2]):
						mc = c1
					else:
						mc = c2
				if not mc:
					break
				if self.compare(self.d[mc], self.d[index]):
					(self.d[mc], self.d[index]) = (self.d[index], self.d[mc])
					index = mc
				else:
					break
		return top

	def __str__(self):
		return str(self.d[1:])
total = int(input())
maxHeap = Heap('MAX')
minHeap = Heap()
ls = []
for i in range(total):
	v = int(input())
	ls.append(v)
	median = 0.0
	maxHeap.add(v)
	minHeap.add(maxHeap.pop())
	if minHeap.size() - maxHeap.size() > 1:
		maxHeap.add(minHeap.pop())
	if minHeap.size() > maxHeap.size():
		median = minHeap.top()
	else:
		median = (maxHeap.top() + minHeap.top()) * 0.5
	median = int(median * 10.0)
	print(median / 10.0)


from heapq import heappush, heappop

class Running_Median_Solver:

	def __init__(self):
		self.left_half = []
		self.right_half = []

	def add_to_left(self, value):
		heappush(self.left_half, -value)

	def pop_from_left(self):
		return -heappop(self.left_half)

	def add_to_right(self, value):
		heappush(self.right_half, value)

	def pop_from_right(self):
		return heappop(self.right_half)

	def add_input(self, value):
		left_len = len(self.left_half)
		right_len = len(self.right_half)
		max = None
		min = None
		if left_len == 0 and right_len == 0:
			self.add_to_left(value)
		else:
			if left_len < right_len or left_len == right_len:
				self.add_to_left(value)
			elif right_len < left_len:
				self.add_to_right(value)
			max = -self.left_half[0]
			min = self.right_half[0]
			if max > min:
				max = self.pop_from_left()
				min = self.pop_from_right()
				self.add_to_left(min)
				self.add_to_right(max)

	def get_median(self):
		left_len = len(self.left_half)
		right_len = len(self.right_half)
		total_len = left_len + right_len
		if total_len % 2 == 1:
			return -self.left_half[0]
		else:
			return (-self.left_half[0] + self.right_half[0]) / 2

def main():
	rms = Running_Median_Solver()
	input_count = int(input())
	while input_count > 0:
		input_value = int(input())
		rms.add_input(input_value)
		print(rms.get_median())
		input_count -= 1
main()


import sys
from heapq import heappop, heappush, heappushpop

class RunningMedian(object):

	def __init__(self):
		self.lower = list()
		self.upper = list()

	def _head_lower(self):
		return -self.lower[0]

	def _head_upper(self):
		return self.upper[0]

	def _add_lower(self, val):
		val = -val
		if len(self.lower) > len(self.upper):
			to_upper = -heappushpop(self.lower, val)
			heappush(self.upper, to_upper)
		else:
			heappush(self.lower, val)

	def _add_upper(self, val):
		if len(self.upper) >= len(self.lower):
			to_lower = -heappushpop(self.upper, val)
			heappush(self.lower, to_lower)
		else:
			heappush(self.upper, val)

	def add(self, val):
		if not self.lower or val <= self._head_lower():
			self._add_lower(val)
		else:
			self._add_upper(val)

	def median(self):
		if len(self.lower) == len(self.upper):
			if len(self.lower) == 0:
				return 0
			else:
				return (self._head_lower() + self._head_upper()) / 2
		else:
			return self._head_lower()

def read_input(reader):
	for line in reader:
		yield int(line)

def main():
	rm = RunningMedian()
	ints = read_input((_.strip() for _ in sys.stdin))
	next(ints)
	for val in ints:
		rm.add(val)
		print(rm.median())
sys.exit(main())


import heapq
smaller = []
bigger = []
for _ in range(int(input())):
	a = int(input())
	if len(smaller) <= 0 or a > -1 * smaller[0]:
		heapq.heappush(bigger, a)
	else:
		heapq.heappush(smaller, -1 * a)
	while len(smaller) - len(bigger) not in [0, 1]:
		if len(smaller) > len(bigger):
			heapq.heappush(bigger, -1 * heapq.heappop(smaller))
		else:
			heapq.heappush(smaller, -1 * heapq.heappop(bigger))
	if len(smaller) - len(bigger) == 1:
		print(float(-1 * smaller[0]))
	elif len(smaller) - len(bigger) == 0:
		print((-1 * smaller[0] + bigger[0]) / 2)


from heapq import *
import sys
size = int(sys.stdin.readline())
ltheap = []
gtheap = []
for i in range(size):
	n = int(sys.stdin.readline())
	if i == 0:
		heappush(gtheap, n)
	else:
		mid = gtheap[0]
		if n <= mid:
			heappush(ltheap, -1 * n)
		else:
			heappush(gtheap, n)
	if len(gtheap) > len(ltheap) + 1:
		mid = heappop(gtheap)
		heappush(ltheap, -1 * mid)
	elif len(ltheap) > len(gtheap) + 1:
		mid = -1 * heappop(ltheap)
		heappush(gtheap, mid)
	if len(gtheap) == len(ltheap):
		median = (-1 * ltheap[0] + gtheap[0]) / 2
	elif len(gtheap) > len(ltheap):
		median = gtheap[0]
	else:
		median = -1 * ltheap[0]
	print('%.1f' % median)


import bisect
N = int(input())
l = []
c = 1
for n in range(1, N + 1):
	bisect.insort(l, int(input()))
	if n % 2 != 0:
		median = l[n - c]
		c += 1
	else:
		median = (l[n - c + 1] + l[n - c]) / 2
	print(median)