정수가 하나씩 주어진다.

정수가 홀수 개 입력된 순간마다 지금까지 입력된 수들의 중앙값을 출력하라.

중앙값은 수들을 정렬했을 때 가운데에 있는 값이다.

입력

첫째 줄에 정수의 개수 \(n\)이 주어진다.

둘째 줄부터 \(n\)개의 줄에 정수가 하나씩 주어진다.

\(n\)은 홀수이다.

\((1 \le n \le 100000)\)

입력되는 정수는 \(-10^9\) 이상 \(10^9\) 이하이다.

출력

홀수 번째 입력이 들어올 때마다 중앙값을 한 줄에 하나씩 출력한다.

예제 입력

5
5
1
9
3
7

예제 출력

5
5
5