<p>You are given a 2D array of integers <code>envelopes</code> where <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> represents the width and the height of an envelope.</p>

<p>One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope&#39;s width and height.</p>

<p>Return <em>the maximum number of envelopes you can Russian doll (i.e., put one inside the other)</em>.</p>

<p><strong>Note:</strong> You cannot rotate an envelope.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[5,4],[6,4],[6,7],[2,3]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The maximum number of envelopes you can Russian doll is <code>3</code> ([2,3] =&gt; [5,4] =&gt; [6,7]).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[1,1],[1,1],[1,1]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= envelopes.length &lt;= 10<sup>5</sup></code></li>
	<li><code>envelopes[i].length == 2</code></li>
	<li><code>1 &lt;= w<sub>i</sub>, h<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Seg{
    private:
    int n; vector<int> t;
    void build(vector<int>& a, int v, int tl, int tr){
        if(tl==tr){
            t[v]=a[tl];
            return;
        }
        int tm=(tl+tr)/2;
        build(a,2*v,tl,tm); build(a,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    void update(int v, int tl, int tr, int idx, int val){
        if(tl==tr){
            t[v]=max(t[v],val);
            return;
        }
        int tm=(tl+tr)/2;
        if(idx<=tm){
            update(2*v,tl,tm,idx,val);
        }
        else{
            update(2*v+1,tm+1,tr,idx,val);
        }
        t[v]=max(t[2*v],t[2*v+1]);
    }
    int query(int v, int tl, int tr, int l, int r){
        if(l>r) return 0;
        if(tl==l and tr==r){
            return t[v];
        }
        int tm=(tl+tr)/2;
        int ret=query(2*v,tl,tm,l,min(r,tm));
        ret=max(ret,query(2*v+1,tm+1,tr,max(tm+1,l),r));
        return ret;
    }
    public:
    Seg(vector<int> &v){
        n=v.size();
        t.resize(4*n);
        build(v,1,0,n-1);
    }
    void update(int idx, int val){
        update(1,0,n-1,idx,val);
    }
    int query(int l, int r){
        return query(1,0,n-1,l,r);
    }
};
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end());
        int n=envelopes.size();
        vector<int> dp(n);
        vector<int> v(1e5+1);
        Seg st(v);
        int ans=0;
        vector<pair<int,int>> vp; int buf=-1;
        for(int i=0;i<n;i++){
            int h=envelopes[i][0]; int w=envelopes[i][1];
            if(h!=buf){
                while(!vp.empty()){
                    int w1=vp.back().first; int upd=vp.back().second;
                    st.update(w1,upd);
                    vp.pop_back();
                }
                buf=h;
            }
            // cout<<h<<" "<<w<<"\n";
            int maxi=st.query(0,w-1);
            cout<<maxi<<"\n";
            dp[i]=maxi+1;
            vp.push_back({w,dp[i]});
            
            // cout<<dp[i]<<"\n";
            ans=max(ans,dp[i]);
        }
        cout<<dp.back()<<"\n";
        return ans;

    }
};
256696