실시간 중앙값

은하는 주식 시장에서 실시간으로 주가를 관찰하고 있다. 새로운 주가가 들어올 때마다 지금까지 관찰한 모든 주가의 중앙값을 기록하려고 한다.

관찰한 주가의 개수가 홀수이면 중앙값은 정렬했을 때 가운데 값이고, 짝수이면 가운데 두 값 중 작은 값을 중앙값으로 한다.

매 초마다 하나의 주가가 주어질 때, 각 시점에서의 중앙값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 관찰할 주가의 수 N이 주어진다. (1 <= N <= 100,000)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 1 이상 1,000,000,000 이하이다.

출력

N개의 줄에 걸쳐 각 시점의 중앙값을 출력한다.

입출력 예시

입력 1

5
1 2 3 4 5

출력 1

1
1
2
2
3

입력 2

5
5 4 3 2 1

출력 2

5
4
4
3
3