Bob And The Tasks

4

2 votes
Basics of Greedy Algorithms, Greedy Algorithms, Algorithms
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 ith day he has to perform the Xth 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<=105

1<=A[i]<=N

0<=K<=105

Sample Input
2
1 1
1
4 1
1 2 4 3
Sample Output
-1
3
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.

Editor Image

?