RMID - Running Median


You will be given some integers in non decreasing order and each time the median is queried you have to report and remove it. Take the smaller element as median in case of even elements.

Input

The input contains many test cases. Read until End Of File.

Each test case contains n (n ≤ 100000) positive integers in non-decreasing order, along with m queries indicated by -1, all on separate lines. (See the example.)

For a query, print the current median on a single line and remove it from the list. 

Each test case ends with 0 on a single line, and two test cases will be separated by an empty line. All integers are guaranteed to fit in a signed 32-bit container. A query can only occur if the list is non-empty. 

Output

For each test case output m lines containing the answers to the corresponding queries. Print an empty line after each test case. 

Example

Input:
1
2
3
4
-1
-1
5
6
7
-1
0

2
3
-1
0

Output:
2
3
5

2

hide comments
kenobi: 2017-06-23 15:40:30

cstdio + vector works for me

itachi_2016: 2017-06-15 12:01:34

Last edit: 2017-06-15 12:11:42
sas1905: 2017-06-05 17:58:25

BIT+binary search :)

Juan: 2017-04-25 12:47:13

Time constraints are way too hardcore for interpreted languages, exactly same solution passes in C, but gives TLE in java even buffering in java but not in c, using 2 static global arrays to keep both the stack and the queue ...
nice problem but please take a look at time constraints

surayans tiwari(http://bit.ly/1EPzcpv): 2017-02-16 07:52:35

can be done using multiset + bin search

vengatesh15: 2016-12-26 10:05:01

AC in 1 go used both stack and queue

Anuj Arora: 2016-08-28 12:17:51

Phew...a few minor optimizations....and accepted....nice list question

naruto09: 2016-03-31 16:49:46

Ok unexpected AC...!!

DEVVRAT GUPTA: 2015-12-25 05:29:11

50th AC

MAYANK NARULA: 2015-12-15 12:30:55

why does it TLE??.........
I used a doubly linked list and maintained a head node for start,end,mid pointers..also storing count..


Added by:jayant mukherji
Date:2013-07-12
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET