절댓값 힙

• 최소 힙, 최대 힙 에 이어지는 우선순위 큐 (Priority Queue) 문제.
• 이번에는 절댓값을 키값으로 갖는다. 절댓값과 원래값을 튜플로 묶어서 heapq 모듈을 사용하도록 하자.
• 삽입과 삭제의 시간 복잡도는 여전히 O(logn)이므로, 전체 시간 복잡도는 O(nlogn)

"""Solution code for "BOJ 11286. 절댓값 힙".

- Problem link: https://www.acmicpc.net/problem/11286
- Solution link: http://www.teferi.net/ps/problems/boj/11286

Tags: [Heap]
"""

import heapq
import sys


def main():
    N = int(sys.stdin.readline())
    heap = []
    for _ in range(N):
        x = int(sys.stdin.readline())
        if x == 0:
            print(heapq.heappop(heap)[1] if heap else '0')
        else:
            heapq.heappush(heap, (abs(x), x))


if __name__ == '__main__':
    main()