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
csd_123:
20201018 13:46:30
gettig error in test case 7 using LIS


pandey101299:
20200715 07:18:58
easy one ,fenwick tree(just try LIS ends with a[i]) 

codificador:
20200528 13:44:54
For those getting WA, just output 1 for any "L" greater than your LIS size. 

embiway:
20191224 04:30:21
Can L be zero?


scolar_fuad:
20191127 20:05:13
Easy problem LIS with binary search


lapokin:
20190811 22:49:34
O(n*log(n) * T) = O(10^6*20*100) = O(20*10^8) => 20 sec??? 

asanyal122:
20190722 09:20:07
LIS nlogn 

rishabh_jiit:
20190110 12:29:14
@mahilewets can you please tell your logic behind this question.


anirudnits:
20180621 10:49:33
just LIS in nlogn. 

shiv2111:
20180104 07:30:05
easy BIT.

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 