import sys
import heapq


def sol():
    # sys.stdin = open("./1655/input.txt")
    input = sys.stdin.readline
    N = int(input())
    min_heap = []
    max_heap = []
    for _ in range(N):
        x = int(input())
        if len(max_heap) == len(min_heap):
            heapq.heappush(max_heap, -x)
        else:
            heapq.heappush(min_heap, x)
        if len(max_heap) > 0 and len(min_heap) > 0:
            if -max_heap[0] > min_heap[0]:
                max_heap_top = -heapq.heappop(max_heap)
                min_heap_top = heapq.heappop(min_heap)
                heapq.heappush(max_heap, -min_heap_top)
                heapq.heappush(min_heap, max_heap_top)
        print(-max_heap[0])


if __name__ == "__main__":
    sol()
