non-decreasing-sequence-4

Shinchan and Kazama both are playing with numbers. Shinchan gives Kazama an array of numbers and asks him to tell the minimum possible last number of a non decreasing 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 non decreasing sequence i.e. L.  

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

CONSTRAINTS-
 1 ≤ T ≤ 100  
1 ≤ N ≤ 10^6
1 ≤ a[i] ≤ 10^6
1 ≤ L ≤ N

SAMPLE INPUT
1
7
9 7 2 5 4 11 12 
3

SAMPLE OUTPUT
11

Explanation

In sample input, possible non-decreasing 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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Sorting

Implementation


Solutions:
for _ in range(eval(input())):
	n = eval(input())
	arr= list(map(int, input().split()))
	klen= eval(input())
	minArr = [0] * n
	currLen = 1
	minArr[0] = arr[0]
	for i in range(1, n):
		if arr[i] < minArr[0]:
			minArr[0] = arr[i]
		elif arr[i] > minArr[currLen-1]:
			if currLen < klen:
				minArr[currLen] = arr[i]
				currLen += 1
		else:
			low = -1
			high= currLen - 1
			while low < high:
				mid = low + (high - low) / 2
				if minArr[mid] < arr[i]:
					low = mid + 1
				else:
					high = mid
			minArr[high] = arr[i]
	if currLen < klen:
		print("-1")
	else:
		print(minArr[klen - 1])
				
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def binarysearch(arr,target):
	if target<=arr[0]:
		return 0
	if target>=arr[-1]:
		return len(arr)-1

	low=0
	high=len(arr)-1
	while low<=high:
	   mid=(low+high)/2
	   if arr[mid]==target:
		   return mid
	   elif arr[mid]<target:
		   low=mid+1
	   else:
		   high=mid-1
	return low

if False:
	a=eval(input())
	target=eval(input())
	print("inputs",a,target)
	print(binarysearch(a,target))

def NonDecreaseMin(arr,length):
	n=len(arr)
	stack=[arr[0]]
	for a in arr[1:]:
		if a>=stack[-1]:
			stack.append(a)
		else:
			relocation=binarysearch(stack,a)
			stack[relocation]=a
	if len(stack)<length:
		return -1
	else:
		return stack[length-1]

T=int(input())
for i in range(T):
	input()
	arr=list(map(int,input().split()))
	length=int(input())
	print(NonDecreaseMin(arr,length))