관측대를 가리는 다음 기록

문제

한 천문대는 밤 동안 같은 방향의 하늘을 여러 차례 관측한다. 각 관측에서 얻은 영상에는 선명도를 나타내는 정수 점수가 붙는다. 관측 기록은 얻은 순서대로 배열에 저장되며, 첫 번째 기록부터 N번째 기록까지 차례로 번호가 매겨진다. 관측 간 실제 시간 간격은 서로 다를 수 있지만, 이번 분석에서는 기록 번호의 차이만 사용한다. 연구원은 각 기록이 이후의 더 선명한 기록으로 처음 대체되는 시점을 알고 싶다. i번째 기록에 대해 i보다 뒤에 있으면서 선명도가 i번째 기록보다 엄격하게 큰 기록을 찾는다. 이런 기록이 여러 개라면 번호가 가장 작은 기록을 선택한다. 선택한 기록의 번호를 j라고 할 때, i번째 기록의 대체 간격은 j-i다. 이는 두 기록 사이에 끼어 있는 기록 수가 아니라 두 기록 번호의 차이다. 선명도가 같은 기록은 대체 기록으로 인정하지 않는다. 더 선명한 기록을 찾는 동안 선명도가 낮거나 같은 기록을 몇 개 지나치는지는 제한하지 않는다. 예를 들어 다음 기록의 점수가 같더라도 그 뒤에서 처음 나타나는 더 큰 점수의 기록이 대체 기록이 될 수 있다. 한 기록이 여러 앞선 기록의 대체 기록으로 동시에 선택되어도 된다. 마지막 기록처럼 뒤에 기록이 없거나, 뒤에 있는 모든 기록의 선명도가 현재 점수 이하라면 대체 간격을 0으로 정한다. 모든 기록은 원본 배열을 기준으로 독립적으로 판단하며, 대체 기록을 찾았다는 이유로 배열에서 어떤 기록을 삭제하지 않는다. 각 기록의 대체 간격을 원래 기록 순서대로 계산하는 프로그램을 작성한다.

입력

첫째 줄에 관측 기록 수 N이 주어진다. 1 ≤ N ≤ 60,000이다.
둘째 줄에 각 기록의 선명도 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 각 선명도는 0 이상 999 이하의 정수다.

출력

첫 번째 기록부터 N번째 기록까지의 대체 간격 N개를 공백으로 구분하여 한 줄에 출력한다. 더 선명한 뒤쪽 기록이 없으면 해당 위치에 0을 출력한다.

7
5 5 2 8 6 9 9

3 2 1 2 1 0 0

4
9 7 7 1

0 0 0 0

1
0

0

출처: Devin.KR 자체 제작