정수가 하나씩 순차적으로 주어진다.

각 정수가 추가될 때마다 지금까지 입력된 수들의 중앙값을 즉시 출력하라.

원소 개수가 짝수인 경우 두 중앙값 중 작은 것을 출력한다.

입력

첫째 줄에는 입력되는 정수의 개수 N이 주어진다.

N은 1 이상 100,000 이하의 자연수이다. 그 다음 N줄에 걸쳐 정수가 차례대로 하나씩 주어진다.

정수는 -10,000 이상 10,000 이하이다.

출력

각 정수가 입력될 때마다 현재까지 입력된 수들의 중앙값을 한 줄에 하나씩 출력한다.

예제 입력 1

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5