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

# Not sure what is going on here

# Data Structure: Stack to track indices of elements, DP array to store the number of steps for each element
# Algorithm: Monotonic stack to track decreasing sequences and dynamic programming (DP) to store the steps required

# Short Intuition:
# We use a stack to track elements that are part of a decreasing sequence and a DP array to store how many steps it takes for each element to be removed.

# Detailed Intuition:
# - The stack helps in maintaining a monotonic decreasing order of the elements from right to left.
# - The DP array stores, for each element, the number of steps it takes for it to be removed. If an element is smaller than an element before it, we use the DP array to calculate how long it will take for that element to be removed.
# - As we iterate through the array from right to left, for each element, we check how long it will take for it to be removed based on the elements to its right.
# - The maximum value in the DP array will give us the total number of steps required for the entire array to become non-decreasing.

# Pseudo Code:
# 1. Initialize an empty stack and a DP array of size equal to the length of the input array.
# 2. Traverse the input array from right to left.
# 3. For each element, pop the elements from the stack that are smaller and update the DP array.
# 4. Append the current index to the stack.
# 5. Return the maximum value from the DP array.

from typing import List

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        # Step 1: Initialize a stack and DP array
        stack = []  # Monotonic decreasing stack to track elements
        dp = [0] * len(nums)  # DP array to store the steps for each element
        
        # Step 2: Traverse the array from right to left
        for i in range(len(nums)-1, -1, -1):
            # Step 3: Use stack to find how long the current element will take to be removed
            while stack and nums[stack[-1]] < nums[i]:
                dp[i] = max(dp[i]+1, dp[stack.pop()])
            
            # Step 4: Push the current index to the stack
            stack.append(i)
        
        # Step 5: Return the maximum value from the DP array (total steps)
        return max(dp)

# Time Complexity: O(n), where n is the length of the array.
# Explanation: Each element is pushed and popped from the stack at most once, and we update the DP array in constant time.

# Space Complexity: O(n)
# Explanation: Space is used for the stack and the DP array.

675