Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

ICPC World Final

By subhashis_cse · Limits 1s, 512 MB

ICPC (International Collegiate Programming Contest) World final is one of the most prestigious contest in the world. Every year lots of team participate in this contest. Teams from Bangladesh are also participating in this contest since 1997. From Bangladesh every year lots of contestants also try to participate in this World Final. But only few are qualified to participate in this contest.

Amin,from Bangladesh, wanted to participate in this World Final to represent his country and university also. He solved a lot of problems and participated in a lots of online & onsite contests too. After working his heart out finally he participated in the ICPC World Final. Now here I will give you an array of integers which will indicate the number of solved problems by Amin on each day. And you have to find the non decreasing sub-sequence of length Y and output the minimum possible maximum number.

Input

The first line contains one integers t (1<=t<=100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1<=n<=10^6) the number of days.

The second line of each test case contains n integers a1,a2,a3…..an (1<=ai<=10^6)-the elements of array. Here ai will indicate the solved problems of ith day by Amin.

Next line contains length of the non decreasing sub-sequence i.e Y. (1<=Y<=n)

It is guaranteed that the sum of n for all test cases does not exceed 10^6 (∑n<=10^6).

Output

You have to find the non decreasing sub-sequence of length Y and output the minimum possible maximum number & if not possible output “-1”.

Sample

InputOutput
2
7
3 5 2 4 7 1 9
3
5
4 3 2 1 2 
3

Case 1: 7
Case 2: -1

In the first case,possible non-decreasing sub-sequences of length Y=3 are [3,5,7], [3,5,9], [3,4,7], [3,4,9], [3,7,9], [5,7,9], [2,4,7], [2,7,9], [2,4,9], [4,7,9] and the minimum possible maxium number is 7 for the sub-sequence [2,4,7].Hence the answer is 7.

For the second case,there are no possible non-decreasing sub-sequence of length 3 so that the answer is -1.

    Discussion

    Statistics


    74% Solution Ratio

    AashiqEarliest, 3M ago

    TurinhstuFastest, 0.1s

    Ashraful_jnuLightest, 1.0 MB

    MursaleenShortest, 492B

    Submit

    Login to submit

    Related Contests