백준 1655 [python]

https://www.acmicpc.net/problem/1655

import sys
import heapq
MAX = 10001

n = int(input())
l = []
left_heap = []
right_heap = []
mid = MAX

for i in range(n):
    a = int(sys.stdin.readline())
    
    if mid == MAX:
        mid = a
        print(mid)
        continue
    
    if a >= mid: heapq.heappush(right_heap, a)
    else: heapq.heappush(left_heap, (-a, a))
    
    if len(right_heap) == len(left_heap) + 2:
        heapq.heappush(left_heap, (-mid, mid))
        mid = heapq.heappop(right_heap)
    elif len(left_heap) == len(right_heap) + 2:
        heapq.heappush(right_heap, mid)
        temp, mid = heapq.heappop(left_heap)
    
    if len(right_heap) == len(left_heap) or len(right_heap) == len(left_heap) + 1:
        print(mid)
    else:
        print(left_heap[0][1])

내 힘으로 풀려다 실패했다. 아이디어가 안 떠오른다. 힙을 두 개 쓴다는 힌트만 얻고 풀었다. 정답 코드를 보니 나처럼 중간값을 밖에 빼서 더럽게 하지 않고 힙에 넣으니 더 깔끔했다.