Bob And The Tasks

★★★★★

2 votes

Basics of Greedy Algorithms, Greedy Algorithms, Algorithms

Details

Problem

Bob has been assigned $N$ tasks arranged in a row, and in one day, he can perform one task. So, to perform all of the $N$ tasks, he will take $N$ days.

He has been given an array $A$ containing $N$ integers where $A[i] = X$ denotes that on the $i^{th}$ day he has to perform the $X^{th}$ task.

Bob has been given an integer $K$ and has to tell the minimum days he will take to reach the configuration where there are exactly $K$ tasks between a pair of completed tasks, and all these $K$ tasks are not completed.

Help Bob to find the minimum days to reach the configuration mentioned above or print $-1$ if it's impossible.

Input Format:

The first line contains a single integer $T$ , denoting the number of test cases.
The first line of each test case contains two spaced integers, $N$ and $K$ .
The second line of each test case contains $N$ space-separated integers, denoting the elements of the array $A$ .

Output Format:

For each test case, print the minimum days to reach the configuration mentioned in the problem statement. Print $-1$ if it's impossible.

Constraints:

$1 <= T <= 10$

$1 <= N <= 10^5$

$1 <= A[i] <= N$

$0 <= K <= 10^5$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case 1:
There is only one task here, so the given configuration is not possible.

For test case 2:
After the first day, Bob completes the 1st task; the configuration will be [1, 0, 0, 0].
After the second day, he completes the 2nd task; the configuration will be [1, 1, 0, 0].
After the third day, he completes the 4th task; the configuration will be [1, 1, 0, 1].
After the third day, he completes the 3rd task; the configuration will be [1, 1, 1, 1].

We can see that after the 3rd day, there is a configuration where two completed tasks have exactly one (K = 1) not completed task between them. Hence, the answer is $3$ .