<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. In one step, <strong>remove</strong> all elements <code>nums[i]</code> where <code>nums[i - 1] &gt; nums[i]</code> for all <code>0 &lt; i &lt; nums.length</code>.</p>

<p>Return <em>the number of steps performed until </em><code>nums</code><em> becomes a <strong>non-decreasing</strong> array</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [5,3,4,4,7,3,6,11,8,5,11]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The following are the steps performed:
- Step 1: [5,<strong><u>3</u></strong>,4,4,7,<u><strong>3</strong></u>,6,11,<u><strong>8</strong></u>,<u><strong>5</strong></u>,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,<u><strong>4</strong></u>,4,7,<u><strong>6</strong></u>,11,11] becomes [5,4,7,11,11]
- Step 3: [5,<u><strong>4</strong></u>,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.
</pre>

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

<pre>
<strong>Input:</strong> nums = [4,5,7,7,13]
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums is already a non-decreasing array. Therefore, we return 0.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        # 4th try solution decreasing stack  
        # https://leetcode.com/problems/steps-to-make-array-non-decreasing/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days
        res = 0 
        stack = []
        for x in nums: 
            cnt = 1  # Assuming X can be removed, minimum required step is 1            
            while stack and x >= stack[-1][0]:
                cnt = max(cnt, stack.pop()[1] + 1)   # After removing the popped number, we need 1 more step to remove x
            if not stack:            
                # X belongs to the final sequence
                stack.append((x, 0)) 
            else: 
                # There is something bigger than x in the stack, hence it will be removed, push its value to the stack for iterations after
                stack.append((x, cnt))
                res = max(res, cnt)

        return res 
        # third try
        # 5 3 4 4 7 3 6 11 8 5 11 
        #   -----   ---    ---
        #   3        2.     2 
        # so the maximum is 3? 
        ans = 0
        right = 1

        while right < len(nums):
            left = right - 1
            len_segment = 0
            while right < len(nums)-1 and nums[right] - nums[left] < 0:
                if (right == left + 1) or (right > left + 1 and nums[right] >= nums[right-1]):
                    len_segment += 1
                right += 1
                # when nums[right] < nums[right-1], it can be removed in parallel with nums[right-1], so it doesn't need extra step
                # so this shouldn't be counted in len_segment
                # example is the "8 5" in the test case 1, 5 will be removed together with 8
                # in the below example, 5 is not counted, but 9 should be counted
                # 5 3 4 4 7 3 6 11 (8 5 9 9 9 9 9) 11 
            if len_segment != 0:
                ans = max(ans, len_segment)
            else:
                right += 1
        
        return ans 

        # second try - still TLE at the same test case
        # no need to check every pair every time, only need to check the new pair

        # ans = 0
        # negative_indices = set()
        # for i in range(1, len(nums)):
        #     if nums[i] - nums[i-1] < 0:
        #         negative_indices.add(i)

        # if len(negative_indices) > 0:
        #     ans += 1
        
        # indices_removed = negative_indices
        # while len(negative_indices) > 0:
        #     new_negative_indices = set()
        #     for i in negative_indices:
        #         new_pre, new_after = i - 1, i + 1
        #         while new_pre > 0 and new_pre in indices_removed:
        #             new_pre -= 1
        #         while new_after < len(nums) and new_after in indices_removed:
        #             new_after += 1
        #         if new_after not in indices_removed and new_after < len(nums) and nums[new_after] - nums[new_pre] < 0:
        #             # the first condition new_after not in indices_removed is necessary
        #             # because it is possible that the end of the nums are all decreasing and got removed
        #             # so new_after == len(nums) - 1 is also removed
        #             new_negative_indices.add(new_after)

        #     if len(new_negative_indices) > 0:
        #         ans += 1
        #     indices_removed = indices_removed.union(new_negative_indices)
        #     negative_indices = new_negative_indices

        # return ans

 
        # first trial - TLE - when most part of the nums is increasing, it's slow to find negagive
        # ans = 0

        # pre = nums[0:-1]
        # after = nums[1:]
        # diff = [n1 - n2 for n1, n2 in zip(after, pre)] 

        # find_decreasing = False
        # negative = []
        # for i in range(len(diff)-1, -1, -1): # reverse order, so that the index wont be impacted
        #     if diff[i] < 0:
        #         negative.append(i + 1) # the indices that should be pop out in nums

        # if len(negative) > 0:
        #     find_decreasing = True
        #     ans += 1
        #     for n in negative:
        #         nums.pop(n)
        

        # while find_decreasing:
        #     pre = nums[0:-1]
        #     after = nums[1:]
        #     diff = [n1 - n2 for n1, n2 in zip(after, pre)] 

        #     negative = []
        #     for i in range(len(diff)-1, -1, -1): # reverse order, so that the index wont be impacted
        #         if diff[i] < 0:
        #             negative.append(i + 1) # the indices that should be pop out in nums

        #     if len(negative) > 0:
        #         ans += 1
        #         for n in negative:
        #             nums.pop(n)
        #     else:
        #         find_decreasing = False

        # return ans


737