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

ANSWER

#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;
}