* 겪고 있는 문제 상황을 최대한 자세하게 작성해주세요.

* 문제 해결을 위해 어떤 시도를 해보았는지 구체적으로 함께 알려주세요.

https://www.acmicpc.net/problem/2493

위 문제 풀었는데, 단조증가 스택 사용해서 풀었습니다.

그런데 이게 스택 내용물을 pop 할때 반드시 하나만 pop 하는게 아닌데

(이미 9,7,6,5 가 쌓여있는데 다음 차례가 8일 경우)

왜 시간복잡도가 O(N)이라 하는건지 잘 감이 안옵니다.

import sys
input = sys.stdin.readline
N = int(input())
cnt = 0
B = []
arr = ['0'] * N
for b in list(map(int,input().split())):
    B.append((b, cnt))
    cnt += 1
stk = []
ln = 0
for b in B:
    while stk:
        # 자기보다 작으면 pop (단조증가수열 유지용)
        if(stk[-1][0] <= b[0]):
            stk.pop(-1)
        else:
            arr[b[1]] = str(stk[-1][1] + 1)
            # 자기보다 크거나 작은걸 만나면 이후 아무것도 안하면 됨 + 루프방지
            break
    # 일단 자기 자신은 스택의 맨 위에 놓는다
    stk.append(b)
print(' '.join(arr))