운동 기록의 앞선 고중량

문제

헬스장의 운동 기록 서비스는 회원이 같은 운동 기구로 수행한 세트들을 시간순으로 저장한다. 한 회원의 기록에는 총 N개의 세트가 있으며, 가장 먼저 수행한 세트부터 차례대로 1번부터 N번까지 번호가 붙어 있다. i번 세트에서 사용한 중량은 양의 정수 W_i이다. 이 문제에서는 운동 횟수나 휴식 시간은 고려하지 않고, 세트의 순서와 중량만 사용한다. 서비스 개발자는 각 세트 옆에 이전 고중량 기록까지의 거리를 표시하려 한다. i번 세트의 이전 고중량 기록이란 번호가 i보다 작으면서 중량이 W_i보다 엄격히 큰 세트 중 번호가 가장 큰 세트를 뜻한다. 같은 중량으로 수행한 세트는 고중량 기록에 포함하지 않는다. 이전 세트들 가운데 가장 무거운 세트를 고르는 것이 아니라, 조건을 만족하는 세트 중 현재 세트에 가장 가까운 것을 골라야 한다. 조건을 만족하는 세트의 번호가 j이면 i번 세트에 표시할 거리는 i-j이다. 따라서 바로 앞 세트가 현재 세트보다 무거우면 거리는 1이다. 두 세트 사이에 놓인 세트의 개수와는 값이 다를 수 있으므로, 거리는 반드시 두 번호의 차이로 계산한다. 현재 세트보다 무거운 이전 세트가 하나도 없다면 표시할 값은 0이다. 첫 번째 세트에는 이전 기록이 없으므로 항상 0을 표시한다. 모든 세트의 기록은 원래 순서대로 유지된다. 어떤 세트의 표시값을 계산했다고 해서 실제 운동 기록이 삭제되거나 중량이 바뀌지는 않는다. 각 세트의 표시값은 입력으로 주어진 전체 기록에서 자신보다 앞선 세트들을 기준으로 독립적으로 정의된다. 같은 중량이 연속하거나, 중량이 계속 증가하거나 감소하는 기록도 주어질 수 있다. 회원의 세트별 중량이 주어질 때, 서비스에 표시할 N개의 거리를 번호 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 세트의 개수 N이 주어진다. 둘째 줄에 정수 W_1, W_2, ..., W_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 200,000
1 ≤ W_i ≤ 10^9
모든 입력값은 정수이다.

출력

1번부터 N번까지 각 세트에 표시할 거리를 공백으로 구분하여 한 줄에 출력한다. 자신보다 무거운 이전 세트가 없는 위치에는 0을 출력한다.

6
4 2 2 5 3 5

0 1 2 0 1 0

4
9 7 5 3

0 1 1 1

3
6 6 6

0 0 0

출처: Devin.KR 자체 제작