NDS - Increasing numbers


Subham and Dewang both are playing with numbers. Subham gives Dewang an array of numbers and asks him to tell the minimum possible last number of a increasing sequence of length L.

Note: Check the sample I/O for more clarity.

Input

Input consists of number of test cases T. Each test case contains size of array i.e N. Next line contains N space separated elements of array. Next line contains length of the increasing sequence i.e. L.

Constraignts

1 ≤ T ≤ 100
0 ≤ N ≤ 106
0 ≤ a[i] ≤ 106

Output

You have to print the minimum possible last number of a sequence and if their is no increasing sequence of length L, then print "-1" without the quotes.

Example

Input:
1
7
9 7 2 5 4 11 12 
3

Output:
11

Explanation

In sample input, possible increasing sequences of length L = 3 are (9, 11, 12), (7, 11, 12), (2, 5, 11), (2, 4, 11), (2, 5, 12), (2, 4, 12), (2, 11, 12), (5, 11, 12), (4, 11, 12) and the minimum last number is 11 for the sequences (2, 5, 11) and (2, 4, 11). Hence, the answer is 11.

 


hide comments
mahilewets: 2017-09-06 11:59:01

Fenwick tree enough.

pradeep_yadav: 2017-09-01 19:11:48

longest increasing subsequence in O(nlogn) time :)

hacruse: 2017-08-09 19:59:48

Last edit: 2017-08-09 20:00:53
Shubhojeet Chakraborty: 2017-01-24 09:40:18

The sequence should be 'strictly' increasing.

Sushovan Sen: 2016-07-07 10:16:32

@pranav_arora: Your code will run upto last test case even if it fails in first test case.

pranav_arora: 2016-07-06 21:52:20

@author: What do you mean by first test case? The sample test? Spoj shows me that it runs upto the 7th test and then gets wa. :/

aditya730: 2016-07-06 19:10:21

@buttman use assert statements or simply if(l>n){l=l/0 ;} division by zero will give a SIGFPE error.

Re : Okay, I omitted that part from the constraints.

Last edit: 2016-07-06 19:43:41
pranav_arora: 2016-07-06 18:24:24

@author: Can you please check my submission? Am I getting wa on all cases? :/

Re : I tried the first test case, WA on that

Last edit: 2016-07-06 19:43:07
buttman: 2016-07-06 17:50:15

@aditya730 : how can you know that ?

Last edit: 2016-07-06 17:50:39
aditya730: 2016-07-06 17:26:21

In constraints you have mentioned that l<=n whereas there are test cases where l>n.


Added by:Buttman
Date:2016-07-06
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY