Jack Vs Jill
Jack and Jill got into a serious fight. Jack didn't not belive Jill when she said that her memory was far better than the others. He asked her to prove it as follows :-
- Jack would dictate a long list of numbers to her. At any point after he has dictated at least "k" numbers, he can ask her what is the k-th minimum number (the k-th number if the numbers are arranged in increasing order) in the list so far.
- She succeeds in proving herself if she can tell the k-th minimum number every time he asks.
- The number of queries (dictate a new number or ask her the k-th minimum of the numbers given till then) has to be pre-decided before he starts asking.
Jill succeeded in proving herself by convincing Jack quite a few times. Now, Jill remembered that Jack had claimed that he was good at programming. It's her turn to ask him to prove his skill. Jack doesn't want to lose to her and comes to you for help. He asks you to make the program for him.
Jill has agreed to let Jack decide the format of the input and here's what he has decided. First line of the input contains n, the number of queries. Next line contains k. Next n lines contain a query each, say q. If q >= 0 then the number is being 'dictated' to the system and needs to be remembered. If q = -1, then your program should return the k-th minimum number presented so far . It is given that 'q' can be -1 only if at least k numbers have already been given.
For every q = -1, you have to output the k-th minimum number given as input so far (not counting -1 as an input)
Input1: 6 2 3 2 -1 -1 1 -1 Output1: 3 3 2
Input2: 10 5 3 6 1 4 2 9 3 1 0 -1 Output2: 3
|Time Limit:||0.586667 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions