# https://programmers.co.kr/questions/9454
def solution(prices):
    stack = []
    answer = [0 for _ in range(len(prices))]

    # 마지막은 무조건 0이므로 뒤에서 두번째부터 시작
    for i in range(len(prices) - 2, -1, -1):
        count = 0

        # 스택에서 주식이 떨어지기 전까지의 값을 모두 꺼내서 합산
        while len(stack) != 0 and stack[-1][0] >= prices[i]:
            count += stack.pop(-1)[1]

        # (합산 값 + 1)이 가격이 떨어지지 않은 기간 -> 스택에 다시 담기(압축해서 다시 넣는 셈)
        stack.append((prices[i], count + 1))
        answer[i] = stack[-1][1]

    return answer


# 정확성  테스트
# 테스트 1 〉	통과 (0.01ms, 10MB)
# 테스트 2 〉	통과 (0.05ms, 10.2MB)
# 테스트 3 〉	통과 (0.38ms, 10.3MB)
# 테스트 4 〉	통과 (0.44ms, 10.3MB)
# 테스트 5 〉	통과 (0.49ms, 10.4MB)
# 테스트 6 〉	통과 (0.03ms, 10.2MB)
# 테스트 7 〉	통과 (0.27ms, 10.2MB)
# 테스트 8 〉	통과 (0.32ms, 10.3MB)
# 테스트 9 〉	통과 (0.03ms, 10.2MB)
# 테스트 10 〉	통과 (0.51ms, 10.3MB)
# 효율성  테스트
# 테스트 1 〉	통과 (46.52ms, 18.8MB)
# 테스트 2 〉	통과 (32.01ms, 17.6MB)
# 테스트 3 〉	통과 (50.59ms, 19.5MB)
# 테스트 4 〉	통과 (35.65ms, 18.2MB)
# 테스트 5 〉	통과 (27.24ms, 17.1MB)
# 채점 결과
# 정확성: 66.7
# 효율성: 33.3
# 합계: 100.0 / 100.0

assert (solution([1, 2, 3, 2, 3]) == [4, 3, 1, 1, 0])
