Chef and his software
All submissions for this problem are available.
Chef is an IT engineer in a banking company. He is designing a software for maintaining the transactions but is stuck on a feature. Your task is to help Chef by designing the feature, which is, when entering the value of N transactions, it prints the Kth highest transaction from the records at each insertion.
Note: The values of all transaction will be distinct values.
- The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines.
- The first line of each test case contains two space separated integers K and N .
- In the next line there are N space separated values of the transaction.
For each test case in a new line, print the space separated values denoting the Kth highest transaction value at each insertion, if the Kth highest transaction at a particular insertion doesn't exist in the records then print -1.
Print n lines.
- 1 ≤ T ≤ 10
- 1 ≤ N, K ≤ 106
- 1 ≤ Ni ≤ 109
Input: 2 4 6 1 2 3 4 5 6 1 4 4 3 6 5 Output: -1 -1 -1 1 2 3 4 4 6 6
Test Case 1: K = 4, N = 6
|1||-1||No 4th highest transaction.|
|1, 2||-1||No 4th highest transaction.|
|1, 2, 3||-1||No 4th highest transaction.|
|1, 2, 3, 4||1||Here 4th highest transaction is 1.|
|1, 2, 3, 4, 5||2||Here 4th highest transaction is 2.|
|1, 2, 3, 4, 5, 6||3||Here 4th highest transaction is 3.|
Test Case 2: K = 1, N = 4
|4||4||Here 1st highest transaction is 4.|
|4, 3||4||Here 1st highest transaction is 4.|
|4, 3, 6||6||Here 1st highest transaction is 6.|
|4, 3, 6, 5||6||Here 1st highest transaction is 6.|
|Time Limit:||1 - 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.