[백준] 6198번 옥상 정원 꾸미기 문제! (gold 5

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> find=new Stack<>();
        int n=Integer.parseInt(br.readLine());
        int[] building=new int[n+2];
        building[n+1]=1000000001;
        for(int i=1; i<building.length-1; i++){
            building[i]=Integer.parseInt(br.readLine());
        }
        for(int i=1; i<building.length;){
            if(find.size()==0 || building[find.peek()]>building[i]){
                find.push(i);
                i++;
            }
            else {
                building[find.peek()] = i - find.pop() - 1;
            }
        }

        long total=0;
        for(int i=1; i<n+1; i++){
            total+=building[i];
        }
        bw.write(total+"");
        bw.flush();
    }

}