Shifu and his Army
All submissions for this problem are available.Commander Shifu is preparing his army. His cadet has given him a troop of $N$ soldiers, each of them having a specific associativity $a_i$. If two soldiers have the same associativity value, they tend to form a group i.e. they will go to war together whatsoever the orders are. Commander Shifu orders them to stand in a queue in increasing order of their associative value. Shifu has $K$ wars to fight. He fights them one by one. In each war, $Y$ no of enemies come to the war. Shifu has to send at least $Y$ no of soldiers so that they win the war and come back safe. Shifu doesn’t want to tire his soldiers, thus he sends the least possible no of soldiers. If he can’t send at least $Y$ no of soldiers, he knows that he will lose that war and refuses to send any of the soldiers. After a war is finished, the soldiers join the queue. While the war is going on, the cadet visits the camp and wants to know the minimum associativity value amongst the remaining soldiers. (if all the soldiers are gone for war, then print $-1$) Note: Shifu can’t send the soldiers arbitrarily, he has to send the soldiers from the beginning of the queue. ###Input: The first line contains two integers $N$ and $K$. The second line contains $N$ space-separated integers $a_1,a_2,…,a_N$ denoting the associativity value of the soldiers. Next $K$ lines contain a single integer $Y$. ###Output: For each $K$ lines print the minimum associativity value. ###Constraints: - $1 \leq N \leq 10^5$ - $1\leq a[i] \leq 100$ - $1 \leq K\leq 10^5$ - $1 \leq Y\leq 10^5$ ###Subtasks ##Subtask #1 (40 points) : - $1 \leq N \leq 10^3$ - $1 \leq K \leq 10^3$ ##Subtask #2 (60 points) : Original Constraints ###Sample Input: 8 5 1 2 4 2 5 5 4 4 1 3 9 5 7 ###Sample Output: 2 4 1 5 -1 ###Explanation: The queue in increasing order of associativity value: 1 2 2 4 4 4 5 5 Y=3 : Three soldiers from the beginning of the queue go to war so the answer is the associativity value of the fourth soldier i.e. 4 Y= 9 : Shifu has only 8 soldiers thus he doesn’t send any soldier. Y=5 : Six soldiers from the beginning go to the war.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.