def nextGreater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []   # stores indices, values are decreasing (monotone decreasing)

    for i, val in enumerate(nums):
        # Pop everything smaller — current val is their next greater
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)

    # Remaining indices in stack have no greater element → result stays -1
    return result

# nextGreater([2, 1, 2, 4, 3]) → [4, 2, 4, -1, -1]

# nums1 is a subset of nums2. For each element in nums1,
# find its next greater element in nums2.

from collections import defaultdict

def nextGreaterElement(nums1, nums2):
    next_greater = defaultdict(lambda: -1)
    stack = []

    for val in nums2:
        while stack and stack[-1] < val:
            next_greater[stack.pop()] = val
        stack.append(val)

    return [next_greater[x] for x in nums1]

# Key trick: duplicate the array (nums + nums[:-1]) to handle wrap-around.
# Track by index, not value, to handle duplicates correctly.

def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []   # stores indices

    for i in range(2 * n - 1):
        val = nums[i % n]
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val
        if i < n:
            stack.append(i)

    return result

# nextGreaterElements([1,2,1]) → [2,-1,2]

# How many days until a warmer temperature?
# Stack holds indices of days waiting for their next warmer day.

def dailyTemperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []   # indices, temps are decreasing

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j      # days to wait
        stack.append(i)

    return result

# dailyTemperatures([73,74,75,71,69,72,76,73]) → [1,1,4,2,1,1,0,0]

# For each bar, find the left and right boundary where it's the shortest.
# Stack keeps bars in increasing height order.
# When a shorter bar arrives, pop and calculate area using the popped bar as height.

def largestRectangleArea(heights):
    heights.append(0)      # sentinel to flush remaining stack
    stack = [-1]           # sentinel index
    max_area = 0

    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width  = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# largestRectangleArea([2,1,5,6,2,3]) → 10  (bars 5,6 → 2×5)

# Stack approach: when a taller bar arrives, the popped bar forms a valley.
# Water = (min(left_wall, right_wall) - valley_height) × width

def trap(height):
    stack = []
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left   = stack[-1]
            width  = i - left - 1
            depth  = min(height[left], h) - height[bottom]
            water += depth * width
        stack.append(i)

    return water

# trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6

# Symmetric: use increasing stack, pop when smaller arrives.
# On pop: the current element is the PREVIOUS smaller for nothing yet —
# actually flip: maintain DECREASING to find previous greater, or
# iterate from left pushing and recording stack[-1] before appending.

def previousSmaller(nums):
    result = [-1] * len(nums)
    stack = []   # increasing stack (values)

    for i, val in enumerate(nums):
        while stack and stack[-1] >= val:
            stack.pop()
        result[i] = stack[-1] if stack else -1
        stack.append(val)

    return result

# previousSmaller([4, 5, 2, 10, 8]) → [-1, 4, -1, 2, 2]