class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        N = len(temperatures)
        ans = [0] * N

        # monostack tuple[temp, -idx]
        # Note we store the negative of the index to
        # make comparisons easier.
        s = []
        for i in range(N - 1, -1, -1):
            t = temperatures[i]
            while s and s[-1] < (t, -i):
                s.pop()

            if s:
                ans[i] = -s[-1][1] - i
            s.append((t, -i))
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        N = len(temperatures)
        ans = [0] * N

        s = []
        for i, t in enumerate(reversed(temperatures)):
            while s and s[-1] < (t, i):
                s.pop()

            if s:
                ans[N - 1 - i] = i - s[-1][1]
            s.append((t, i))
        return ans