Untitled

#include<vector>
#include<algorithm>



/* using namespace std;
bool cmp(pair<int,int>&a, pair<int,int>&b){
    if(a.first!=b.first) return a.first<b.fisrt;
    else return a.second>b.second;
} */

bool cmp(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first) {
        return a.first < b.first;
    } else {
        return a.second >b.second;
    }
}

/* int longestIncreasingSubsequence(vector<int> &arr, int n){
    if(n==0) return 0;
    
    vector<int> ans;
    ans.push_back(arr[0]);

    for(int i=1;i<n;i++){  //O(n)
        if(arr[i]>ans.back()) ans.push_back(arr[i]);
        else{
            int index=lower_bound(ans.begin(),ans.end(),arr[i])-ans.begin(); //O(logn)
            ans[index]=arr[i];
        }
    }
    return ans.size();
}
 */


int findMaxEnvelopes(vector<int> &height, vector<int> &width, int n) {
    vector<pair<int,int>> env;
    for(int i=0;i<n;i++){
        env.push_back(make_pair(width[i],height[i])); //(width,height)
    }

    sort(env.begin(),env.end(),cmp); //sort based on weught

    vector<int> ans;  //do LIS based on height
    ans.push_back(env[0].second); 

    for(int i=1;i<n;i++){
        if(env[i].second >ans.back()) ans.push_back(env[i].second);
        else{
            int index=lower_bound(ans.begin(),ans.end(),env[i].second) -ans.begin();
            ans[index]=env[i].second;
        }
    }
    return ans.size();
}