오큰수

• Monotone Stack 기법을 사용해서 푸는 전형적이고 대표적인 문제.
• 기본은 아직 오큰수가 결정되지 않은 원소들을 스택에 저장하는 것. 이 원소들은 내림차순으로 유지될수밖에 없다 (top에 가장 작은 원소가 있도록). x라는 새 원소가 들어오면, 스택에서 x보다 작은수들을 모두 pop하고, x를 push한다. 이렇게 하면 스택안의 원소는 내림차순으로 유지되고, 이때 pop한 원소들의 오큰수는 x가 된다.
• 모든 원솟들에 대해서 1번의 push와 1번의 pop가 일어나므로, amortized 시간복잡도 O(n)이 된다.
• pop되는 원소들에 대해서 오큰수를 저장하려면, 원소들의 원래 배열에서의 인덱스도 알고 있어야 한다. 스택 안에 (값,인덱스)의 튜플을 저장하도록 할수도 있고, 그냥 인덱스만 저장해놓고서, 값을 비교할때에는 원래 배열을 통해서 값을 구한 뒤에 비교하는 방법도 있다. 여기에서는 후자로 구현.

"""Solution code for "BOJ 17298. 오큰수".

- Problem link: https://www.acmicpc.net/problem/17298
- Solution link: http://www.teferi.net/ps/problems/boj/17298

Tags: [MonotoneStack]
"""


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    nge = [-1] * N
    stack = []
    for i, a_i in enumerate(A):
        while stack and a_i > A[stack[-1]]:
            nge[stack.pop()] = a_i
        stack.append(i)

    print(*nge)


if __name__ == '__main__':
    main()