<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>

#pragma GCC optimize("unroll-loops,O3,Ofast") //even 10^8+ also works with this
#pragma GCC target("avx2,avx,fma,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
 
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define rt return;
#define set_bits(a) __builtin_popcountll(a)
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define disp(a) {for(int i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<endl;}
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define inp(a) {for(int i=0;i<(a).size();i++) cin>>(a)[i];}
#define fill(a,b) memset(a, b, sizeof(a))
#define prt(a) cout<<(a)<<endl;
#define endl "\n"
#define NO cout<<"NO"<<endl;
#define YES cout<<"YES"<<endl;
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define double double
#define de(a) cout<<"("<<a<<")"<<endl;
#define de2(a) cout<<"*"<<a<<"*"<<endl;
#define ft front()
#define bk back()
#define minpq priority_queue<ll, vector<ll>, greater<ll> >
#define maxpq priority_queue<ll>
#define nl cout<<endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define cont continue;
#define vpll vector<pair<ll,ll>>
#define vvii vector<vector<int>>
#define vi vector<int>
#define vvpll vector<vector<pair<ll,ll>>>
#define pll pair<ll,ll>

//const ll M=998244353;
const ll M=1e9+7;
const ll N=1e5+5;  
const ll inf=1e18; //keeping inf may not give soln every time,try 1e9, 1e15

ll bit(ll n,ll i){return (n&(1LL<<i)) ? 1 : 0;}

class segtree{//1 based indexed segtree (point update,range query)  type-1
public:
  vector<ll> tree;
  segtree(ll n){
    tree.resize(4*n);
  }
  ll query(ll ind,ll st,ll ed,ll l,ll r){//range query, write @l,r; like update in type-2
     if(l<=st && ed<=r){
      return tree[ind];
     }
     if(r<st || l>ed){
        return 0;//Take care of this it will differ for diff types of queris
     }
     ll mid=(st+ed)>>1;
     ll left = query(2*ind,st,mid,l,r);
     ll right =query(2*ind+1,mid+1,ed,l,r);
     return max(left,right);
  }

  void update(ll ind,ll st,ll ed,ll pos,ll val){//point update
     if(st==ed){
        tree[ind]=max(val,tree[ind]);
        return;
     }
     ll mid=(st+ed)>>1;
     if(st<=pos && pos<=mid){
        update(2*ind,st,mid,pos,val);
     }
     else{
        update(2*ind+1,mid+1,ed,pos,val);
     }
     tree[ind]=max(tree[2*ind],tree[2*ind+1]);
  }
};

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& v){
        ll  n=v.size();
        map<ll,vll> mp;
        for(int i=0;i<n;i++){
          mp[v[i][0]].pb(v[i][1]);
        }
        vll a;
        segtree st(N);
        ll ans=0;
        for(auto it=mp.rbegin();it!=mp.rend();it++){
           vll t=(*it).ss,t2;
           for(auto &k: t){
             ll mx=st.query(1,0,N-1,k+1,N-1);
             ans=max(ans,mx+1);
             t2.pb(mx);
           }
           for(int i=0;i<t.size();i++){
             st.update(1,0,N-1,t[i],t2[i]+1);  
           }
        }
        return ans;
    }
};
292528