All submissions for this problem are available.
Monsoons have just arrived and the scientists in Byteland have developed a strange machine called Rain meter that could tell them the probability of flooding a region. This machine takes as input the amount it had rained (in cm) for a period of last n days and an integer k describing the kth least rainy day. It then performs some weird calculations and gives the result.
Don’t worry. Your task is not that difficult as the scientists in Byteland. You just need to help them to find out the kth least rainy day given the array of rainfalls in last n days. The rainfall in Byteland has two distinct features.
- The rainfall of every day is distinct.
- The rains follow a strange pattern. It keeps on increasing from 1 to ith day (i could be 0 or even n) and then keeps on decreasing from there on.
Given the array of rainfalls and the value of k, you need to find out the kth least rainy day.
The first line of input consists of the number of test cases T. Then T lines follow each describing a test case. The first line of each test case consists of two numbers n and k. The next line consists of n numbers denoting the rainfall of that day. All numbers are space separated and follow the above two rules.
For each test case print a line denoting the kth least rainy day.
1≤ n ≤ 106
1 ≤ k ≤ n
1≤ rainfall in a day ≤ 109
Input: 3 5 3 3 4 5 2 1 4 3 1 2 3 4 8 5 1 4 7 10 9 8 6 2 Output: 3 3 7
|Time Limit:||0.3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.