가운데값 말하기

정수가 하나씩 주어진다. 정수가 추가될 때마다 지금까지 주어진 모든 수를 정렬했을 때의 가운데값을 출력해야 한다.

지금까지 주어진 수의 개수가 짝수이면 가운데에 있는 두 수 중 더 작은 값을 가운데값으로 정한다. 각 순간의 가운데값을 순서대로 구하는 프로그램을 작성하라.

첫째 줄에 주어지는 정수의 개수 N이 주어진다. 1 <= N <= 100,000이다.

다음 N개의 줄에는 정수가 하나씩 순서대로 주어진다. 각 정수 x는 -10,000 <= x <= 10,000을 만족한다.

N개의 줄에 걸쳐, 각 정수가 주어진 직후의 가운데값을 한 줄에 하나씩 출력한다.