import java.util.Stack;

class Solution {
    
    private class Price {
        int index;
        int price;
        
        public Price(int index, int price) {
            this.index = index;
            this.price = price;
        }
    }
    
    private Stack<Price> stack;
    
    public int[] solution(int[] prices) {
        
        int[] answer = new int[prices.length];
        stack = new Stack<>(); // Object 'Price' 1 ~ (i - 1)
        
        
        for (int i = 0; i < prices.length; i++) {
            
            int currentPrice = prices[i];
            
            while (!stack.isEmpty()) {
                Price top = stack.peek(); // get only data
                if (top.price > currentPrice) {
                    answer[top.index] = i - top.index;
                    stack.pop(); // delete top data
                }
                else break; // do nothing
            }
            
            stack.push(new Price(i, currentPrice)); // add data
        }
        
        while (!stack.isEmpty()) {
            Price top = stack.pop(); // get top data and remove it
            answer[top.index] = prices.length - 1 - top.index; // '-1' is important that it catch the condition the last object's price is not down
        }
        
        return answer;
    }
}
/**
[Question]
- prices : 주식가격 (초 단위) -> values: 1 ~ 10,000, length: 2 ~ 100,000
- return 가격이 떨어지지 않은 기간은 몇 초?
**/