문제
통계에 있어서 어떤 몇 개의 수들을 대표하는 값으로 자주 사용되는 것에는,
N과 꺼내는 공들이 주어질 때, 각각에 걸쳐 중앙값들을 출력하는 프로그램을 작성하자.
평균(mean), 최빈값(mode), 중앙값(median)이 있다.
이 문제에서 다룰 것은 중앙값(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≤N＜20,000, 홀수)이 주어지며, 둘째 줄에는 처음에 꺼낸 공에 써져있는 정수가 주어진다. 세 번째 줄부터 (N-1)/2 개의 줄에는 각각 두 개의 정수 P, Q가 주어지는데,
이는 공을 꺼내는 각각의 시행에서 꺼낸 두 개의 공에 써져있는 정수를 의미한다.
입력되는 모든 수는 -30000 이상 30000 이하의 정수이다.
출력
출력은 총 (N+1)/2 줄로 구성되어 있어야 하며 각 줄마다 해당하는 시행까지
꺼낸 모든 공들에 쓰여 있는 정수들의 중앙값을 출력한다.
예제1
입력
7
5
1 2
7 4
6 3
출력
5
2
4
4