<p>You are playing a game that contains multiple characters, and each of the characters has <strong>two</strong> main properties: <strong>attack</strong> and <strong>defense</strong>. You are given a 2D integer array <code>properties</code> where <code>properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>]</code> represents the properties of the <code>i<sup>th</sup></code> character in the game.</p>

<p>A character is said to be <strong>weak</strong> if any other character has <strong>both</strong> attack and defense levels <strong>strictly greater</strong> than this character&#39;s attack and defense levels. More formally, a character <code>i</code> is said to be <strong>weak</strong> if there exists another character <code>j</code> where <code>attack<sub>j</sub> &gt; attack<sub>i</sub></code> and <code>defense<sub>j</sub> &gt; defense<sub>i</sub></code>.</p>

<p>Return <em>the number of <strong>weak</strong> characters</em>.</p>

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

<pre>
<strong>Input:</strong> properties = [[5,5],[6,3],[3,6]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> No character has strictly greater attack and defense than the other.
</pre>

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

<pre>
<strong>Input:</strong> properties = [[2,2],[3,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The first character is weak because the second character has a strictly greater attack and defense.
</pre>

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

<pre>
<strong>Input:</strong> properties = [[1,5],[10,4],[4,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The third character is weak because the second character has a strictly greater attack and defense.
</pre>

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

<ul>
	<li><code>2 &lt;= properties.length &lt;= 10<sup>5</sup></code></li>
	<li><code>properties[i].length == 2</code></li>
	<li><code>1 &lt;= attack<sub>i</sub>, defense<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>&arr) {
        int ans=0;
        sort(arr.begin(),arr.end());
        vector<int>maxVal(100001,0);
        vector<vector<int>>nums;
        for(int i=0;i<arr.size();i++){
            int st=arr[i][0];int maxi=arr[i][1];
           
            while(i+1<arr.size() && arr[i+1][0]==st){
                maxi=max(maxi,arr[i+1][1]);i++;
            }
            nums.push_back({st,maxi});
        }
        stack<int>st;st.push(-1);
        for(int i=nums.size()-1;i>=0;i--){
            while(st.top()!=-1 && nums[st.top()][1]<=nums[i][1]){
                maxVal[nums[i][0]]=max(maxVal[nums[i][0]],nums[st.top()][1]);
                st.pop();
            }
            if(st.top()==-1) {st.push(i);continue;}
            else maxVal[nums[i][0]]=max(maxVal[nums[i][0]],nums[st.top()][1]);
            st.push(i);
        }
        for(int i=0;i<arr.size();i++){
            int v=arr[i][1];
            if(maxVal[arr[i][0]]>v) ans++;
        }
        return ans;

    }
};
//[6,9],[7,10],[10,7]
//[1,10],[4,1],[5,1],[5,9],[6,9],[7,2],[7,10],[10,1]
//[1,10],[4,1],[5,9],[6,9],[7,10],[10,1]
//1->10
//4->10
//5->10
//6->10
178300