쿠키 고르기

쿠키 생산 공장의 수석 프로그래머로서, 여러분은 공장에서 생산하고 포장하는 모든 쿠키가 매우 까다로운 품질 기준을 만족하도록 관리해야 합니다.

생산 라인은 새 쿠키를 계속 구워 대기 구역(holding area)에 쌓아 두고, 쿠키들은 그곳에서 포장을 기다립니다. 때때로 포장 부서에서 대기 구역의 쿠키 한 개를 포장용으로 보내 달라는 요청이 들어옵니다. 대기 구역이 비어 있을 때에는 절대로 포장 요청이 들어오지 않는다고 가정합니다.

상황을 복잡하게 만드는 것은 불시 점검입니다. 점검관은 다음에 포장 부서로 보낼 쿠키 몇 개를 자신들에게 대신 넘기라고 요구할 수 있는데, 그 쿠키들의 모양과 맛이 서로 고르게 보이면 점검을 통과하고 그렇지 않으면 통과하지 못합니다.

다행히 공장에는 쿠키의 지름을 1 나노미터(nm) 정밀도로 측정하는 장비가 있습니다. 점검에 대비하기 위해, 포장 요청이 들어올 때마다 대기 구역에 있는 모든 쿠키 중 지름이 중앙값인 쿠키를 보내기로 했습니다. 지름이 정확히 중앙값인 쿠키가 없으면, 중앙값보다 큰 쿠키 중에서 가장 작은 것을 보냅니다.

구체적으로, 대기 구역의 쿠키를 지름의 오름차순으로 정렬했다고 합시다. 대기 구역에 쿠키가 $c$개 있다면, 요청이 들어왔을 때 정렬된 순서에서 다음 위치(1부터 시작)의 쿠키를 보냅니다.

• $c$가 홀수이면 $\frac{c+1}{2}$번째 쿠키
• $c$가 짝수이면 $\frac{c}{2}+1$번째 쿠키

입력의 각 줄에는 다음 둘 중 하나가 주어집니다.

• 양의 정수 $d$ — 지름이 $d$ nm인 갓 구운 쿠키가 대기 구역에 도착했음을 뜻합니다.
• 기호 # — 포장 부서가 쿠키 한 개를 포장용으로 보내 달라고 요청함을 뜻합니다.

입력은 최대 600,000줄입니다. 첫 번째 쿠키가 도착하기 전에 대기 구역은 비어 있습니다. 또한 공장의 오븐은 지름이 30 센티미터(cm), 즉 300,000,000 nm보다 큰 쿠키는 만들 수 없습니다.

각 포장 요청에 대해, 포장용으로 보낸 쿠키의 지름(nm)을 요청이 처리된 순서대로 한 줄에 하나씩 출력합니다.