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 ≤ 10^{6}
0 ≤ a[i] ≤ 10^{6}
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
shiv2111:
20180104 07:30:05
easy BIT.


mahilewets:
20170906 11:59:01
Fenwick tree enough. 

pradeep_yadav:
20170901 19:11:48
longest increasing subsequence in O(nlogn) time :)


hacruse:
20170809 19:59:48
Last edit: 20170809 20:00:53 

Shubhojeet Chakraborty:
20170124 09:40:18
The sequence should be 'strictly' increasing. 

Sushovan Sen:
20160707 10:16:32
@pranav_arora: Your code will run upto last test case even if it fails in first test case. 

pranav_arora:
20160706 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:
20160706 19:10:21
@buttman use assert statements or simply if(l>n){l=l/0 ;} division by zero will give a SIGFPE error.


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


buttman:
20160706 17:50:15
@aditya730 : how can you know that ? Last edit: 20160706 17:50:39 
Added by:  Buttman 
Date:  20160706 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 