더 저렴한 충전소까지

문제

전기차 여행 안내소가 일방통행 도로에 있는 충전소들의 요금표를 정리한다. 도로에는 충전소 N개가 있으며, 진행 방향을 따라 1번부터 N번까지 번호가 붙어 있다. 각 충전소에는 정수로 표시된 충전 요금이 하나씩 있다. 모든 요금은 같은 양의 전기를 충전할 때 내는 금액이므로 숫자만으로 비교할 수 있다. 안내소는 각 충전소의 전광판에 앞으로 몇 번째 충전소에서 처음으로 더 저렴하게 충전할 수 있는지를 표시하려 한다. 현재 충전소가 i번이라면, i보다 번호가 크면서 요금이 i번의 요금보다 엄격히 작은 충전소 중 번호가 가장 작은 곳을 찾는다. 그 충전소의 번호를 j라고 할 때 전광판에 표시할 값은 j-i다. 이는 두 충전소 사이의 실제 도로 길이가 아니라 번호의 차이다. 요금이 같은 충전소는 더 저렴한 충전소로 인정하지 않는다. 따라서 바로 다음 충전소의 요금이 같더라도 탐색을 계속해야 한다. 반대로 더 저렴한 충전소를 하나 찾았다면, 그보다 뒤에 요금이 더욱 낮은 충전소가 있더라도 고려하지 않는다. 선택 기준은 요금의 최솟값이 아니라 조건을 만족하는 충전소를 처음 만나는 순서다. 차량은 번호가 증가하는 방향으로만 이동하며, 마지막 충전소를 지난 뒤 처음으로 돌아오지 않는다. 따라서 뒤쪽에 더 저렴한 충전소가 하나도 없다면 -1을 표시한다. 마지막 충전소의 전광판에는 항상 -1이 표시된다. 충전소의 요금은 안내판을 만드는 동안 바뀌지 않으며, 충전기의 사용 여부나 대기 차량 수는 고려하지 않는다. 주어진 요금표를 이용하여 모든 충전소의 전광판에 표시할 값을 번호 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. 둘째 줄에 각 충전소의 요금 P1, P2, …, PN이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 180,000이다. 모든 Pi는 1 이상 9 이하의 정수다.

출력

1번부터 N번 충전소까지 전광판에 표시할 정수 N개를 공백으로 구분하여 한 줄에 출력한다. 뒤에 더 저렴한 충전소가 없으면 해당 값으로 -1을 출력한다.

7
5 5 7 3 4 2 2

3 2 1 2 1 -1 -1

4
6 6 6 6

-1 -1 -1 -1

1
9

-1

출처: Devin.KR 자체 제작