6198 - Stack

처음에 DP 생각했으나 아무리해도 n^2이라 스택으로 생각을 바꾸었음
스택에 있는 값을 뺄 때, 그 값이 바라보는 것의 갯수로 생각하면 이것도 n^2

발상 전환 필요했음
스택의 값을 뺄 때, top 이 바라보는 것의 갯수가 아닌, top을 바라보는 건물들의 갯수 == stack의 크기
를 계속해서 더해주면 n연산에 끝낼수 있다

import sys

n = int(input())
order=[]
for _ in range(n):
    order.append(int(sys.stdin.readline().strip()))


st = []
ssum = 0
for ord in order:
    if not st:
        st.append(ord)
    else:
        if st[-1] > ord:
            st.append(ord)
        else:
            while(st and (st[-1] <= ord)):
                st.pop()
                ssum+=len(st)
            st.append(ord)
if st:
    nn = len(st) - 1
    ssum+=(nn*(nn+1))//2
print(ssum)