# Shinchan and Kazama

QUESTION

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\nNote- Check the sample I/O for more clarity.\n\nINPUT-\nEach 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\n\nOUTPUT- \nYou 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.

“TESTCASE_1”: “7\n9 7 2 5 4 11 12 \n3\n###—###SEPERATOR—###—\n11”, “TESTCASE_2”: “2\n33 73 \n1\n###—###SEPERATOR—###—\n33”, “TESTCASE_3”: “14\n72 70 29 77 73 97 12 86 90 61 36 55 67 55 \n7\n###—###SEPERATOR—###—\n-1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){

long n,l,x;

vector<long> st(100005,0);

int top=0;
st[0]=-1;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
if(x>st[top])
st[++top]=x;

else{
long l=1,r=top,mid;
while(l<=r){
long mid=(l+r)/2;
if(st[mid]<x){
l=mid+1;
}
else
r=mid-1;
}
st[l]=x;
}

}
cin>>l;
if(top<l)
cout<<"-1\n";
else
cout<<st[l]<<"\n";

return 0;
}