class Solution {
public:
    
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
		// seq stores the piles
        vector<int> seq;
        
		// create the first pile
        seq.push_back(nums[0]);
		
		// Go through each card
        for(int j=1; j<n; j++){
					
			// Find the left-most pile that can accomodate this card
            int idx = binSearch(seq, nums[j]);
			
            if(idx == -1){
				// If no such pile exists, then create a new pile
                seq.push_back(nums[j]);
            }else{
				// If a pile is found that can accomodate this card,
				// then place this card on top of that pile
                seq[idx] = nums[j];
            }
        }
        
		// The number of piles is the length of the longest increasing subsequence
        return seq.size();
    }
    
	// Binary search to find the left-most pile that can accomodate a card
	// If a pile is found, then it returns the index to that pile
	// If a pile is not found, then return -1
    int binSearch(vector<int> &seq, int i){
        int l=0, h = seq.size()-1, m;
        int res = -1;
        
        while(l<=h){
            m = l+(h-l)/2;
            if(seq[m] >= i){
                res = m;
                h = m-1;
            }else{
                l = m+1;
            }
        }
        
        return res;
    }
};

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
		// Keeps track of the LIS for each element in nums
        vector<int> is(n);
		// Stores the piles
        vector<int> cont;
		// Keeps track of the Longest Decreasing Subsequence from each element in nums
        vector<int> ds(n);
        
        
        // Calculate the increasing sequence
		// Create the first pile
        cont.push_back(nums[0]);
		// The length of LIS for first element is 1
        is[0] = 1;
        
		// Go through each card
        for(int i=1; i<n; i++){
			// Find the leftmost pile that can accomodate this card
            auto it = lower_bound(cont.begin(), cont.end(), nums[i]);
            if(it == cont.end()){
				// If such a pile does not exist
				// then create a new pile
                cont.push_back(nums[i]);
                is[i] = cont.size()-1;
            }else{
			    // If such a pile exists
				// Then put is card on top of that pile
                *it = nums[i];
                is[i] = distance(cont.begin(), it);
            }
        }
        
        // Calculate the decreasing sequence
		// The same steps as above but for the decreasing sequence
        cont.clear();
        cont.push_back(nums[n-1]);
        ds[n-1] = 1;
        for(int i=n-2; i>=0; i--){
            auto it = lower_bound(cont.begin(), cont.end(), nums[i]);
            if(it == cont.end()){
                cont.push_back(nums[i]);
                ds[i] = cont.size()-1;
            }else{
                *it = nums[i];
                ds[i] = distance(cont.begin(), it);
            }
        }
        
		// Find the longest mountain array
        int ans = INT_MAX;
        for(int i=1; i<n-1; i++){
            if(is[i] && ds[i])
                ans = min(ans, n-(is[i]+ds[i]+1));
        }
        
        return ans;
    }
};

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
		// container to store the piles
        vector<int> seq;
        
		// sort the envelopes
		// If two envelopes have the same width, then the envelope with the largest height is placed before
		// This is because we will apply the patience sort algorithm of the heights
        sort(envelopes.begin(), envelopes.end(), [](vector<int> a, vector<int> b){
            return ((a[0] < b[0]) || (a[0] == b[0] && a[1] > b[1]));
        });
            
		// For each envelope
        for(vector<int> e: envelopes){
		    // Find the left most pile that can accomodate the envelope
            int idx = binSearch(seq, e[1]);
            if(idx == -1){
				// If no such pile is found, then create a new pile
                seq.push_back(e[1]);
            }else{
				// If such a pile is found then
				// Make this envelope the top of the pile
                seq[idx] = e[1];
            }
        }
		
		// The number of piles is the length of the LIS
        return seq.size();
    }
    
	// Binary search to find the left most pile that can accomodate a envelope
	// If such a pile exists, then return the index of the pile
	// Else return -1
    int binSearch(vector<int> &seq, int b){
        int low = 0, high = seq.size()-1, mid, res = -1;
        
        while(low <= high){
            mid = low + (high-low)/2;
            if(seq[mid] >= b){
                res = mid;
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        
        return res;
    }
};