통계에서 어떤 수들을 대표하는 값으로 자주 쓰이는 것에는 평균(mean), 최빈값(mode), 중앙값(median)이 있다. 이 문제에서 다룰 것은 중앙값으로, 어떤 수들을 오름차순(혹은 내림차순)으로 정렬했을 때 가운데에 오는 값을 그 수들의 중앙값이라고 부른다.

동현이는 \(N\) (\(N\)은 홀수) 개의 공에 각각 정수를 쓴 뒤 상자에 넣었다. 맨 처음에는 공을 한 개 꺼내고, 그 뒤로는 한 번에 두 개씩 꺼낸다. 이때 꺼낸 공들에 적힌 모든 정수의 중앙값을 매 시행마다 구하는 것이 문제이다.

예를 들어 \(N = 7\), 공에 적힌 수가 각각 \(1, 2, 3, 4, 5, 6, 7\) 이고 처음에 \(5\)번, 그 뒤로 \((1, 2), (7, 4), (6, 3)\) 의 공을 차례대로 꺼냈다면 각 시행의 중앙값은 \(5, 2, 4, 4\) 가 된다.

[1회] 5

[2회] 1 2 5

[3회] 1 2 4 5 7

[4회] 1 2 3 4 5 6 7

\(N\) 과 꺼내는 공들이 주어질 때, 각 시행마다의 중앙값을 출력하는 프로그램을 작성하라.

\(3 \le N < 1{,}000{,}000\) (\(N\)은 홀수)

입력되는 모든 정수의 절댓값은 \(1{,}000{,}000\) 이하이다.

첫째 줄에 \(N\) (\(3 \le N < 1{,}000{,}000\), \(N\)은 홀수) 이 주어진다.

둘째 줄에는 처음에 꺼낸 공에 적힌 정수가 주어진다.

셋째 줄부터 \((N-1)/2\) 개의 줄에는 각각 두 정수 \(P\), \(Q\) 가 주어지며, 이는 각 시행에서 꺼낸 두 공에 적힌 정수를 의미한다.

입력되는 모든 수는 \(-1{,}000{,}000\) 이상 \(1{,}000{,}000\) 이하의 정수이다.

총 \((N+1)/2\) 개의 줄을 출력한다. 각 줄에는 해당 시행까지 꺼낸 모든 공에 적힌 정수들의 중앙값을 출력한다.

riseoj 작성

출처 Original