1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

import heapq

import sys

 

n = int(sys.stdin.readline().rstrip())

min_heap = []

min_len = 0

max_heap = []

max_len = 0

mid = 0

 

 

def max_heap_push(h, v):

    heapq.heappush(h, –v)

 

 

def max_heap_pop(h):

    return –heapq.heappop(h)

 

for i in range(n):

    k = int(sys.stdin.readline().rstrip())

    if i == 0:

        mid = k

    elif min_len == max_len:

        if k >= mid:

            heapq.heappush(min_heap, k)

            min_len += 1

        else:

            heapq.heappush(min_heap, mid)

            max_heap_push(max_heap, k)

            mid = max_heap_pop(max_heap)

            min_len += 1

    elif min_len > max_len:

        if k >= mid:

            max_heap_push(max_heap, mid)

            heapq.heappush(min_heap, k)

            mid = heapq.heappop(min_heap)

            max_len += 1

        else:

            max_heap_push(max_heap, k)

            max_len += 1

    print(mid)