다음 상승 곡 표시

문제

음악 스트리밍 서비스에서 재생 목록에 새로운 안내 표시를 추가하려 한다. 재생 목록에는 N개의 곡이 정해진 순서로 들어 있으며, 각 위치에는 해당 곡의 반응 점수가 기록되어 있다. 반응 점수는 0 이상의 정수이다. 같은 곡이 여러 번 들어 있거나 여러 위치의 점수가 같더라도 재생 목록의 각 위치는 따로 취급한다. 안내 표시는 현재 위치보다 뒤에 있으면서 현재 곡보다 반응 점수가 높은 곡을 알려 준다. 조건에 맞는 곡이 여러 개이면 재생 목록에서 가장 먼저 만나는 곡을 선택한다. 즉, 현재 위치가 i이면 j > i이고 j번 곡의 점수가 i번 곡의 점수보다 큰 위치 중 가장 작은 j를 선택한다. 점수가 같은 곡은 선택 대상이 아니다. 서비스 화면에는 선택한 곡의 번호나 점수 대신 현재 위치에서 그 곡까지의 이동 거리를 표시한다. 선택한 위치가 j이면 표시할 값은 j - i이다. 바로 다음 곡이 선택되면 1을 표시하며, 중간에 두 곡을 지나야 선택한 곡에 도착한다면 3을 표시한다. 이 거리는 재생 시간과 관계없이 위치 차이만으로 계산한다. 현재 위치 뒤에 점수가 더 높은 곡이 하나도 없다면 0을 표시한다. 마지막 위치에는 뒤에 곡이 없으므로 언제나 0을 표시한다. 재생 목록은 끝에서 처음으로 이어지지 않으며, 현재 위치보다 앞에 있는 곡은 점수가 아무리 높아도 후보가 될 수 없다. 모든 안내 표시는 입력으로 주어진 동일한 재생 목록을 기준으로 계산한다. 한 위치의 표시를 계산했다고 해서 곡을 삭제하거나 순서를 바꾸지 않는다. 또한 선택한 곡이 다른 위치에서도 선택되는 것은 허용한다. 예를 들어 점수가 차례로 4, 4, 7이면 앞의 두 위치는 모두 마지막 위치를 선택하지만 표시할 거리는 서로 다르다. 재생 목록의 각 위치에 표시할 거리를 원래 순서대로 구한다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 각 위치의 반응 점수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 점수는 정수이며 0 ≤ A_i ≤ 1,000,000,000이다.

출력

각 위치에 표시할 거리 N개를 재생 목록 순서대로 한 줄에 공백으로 구분하여 출력한다. 조건에 맞는 뒤쪽 위치가 없으면 해당 위치에는 0을 출력한다.

6
4 4 7 2 5 8

2 1 3 1 1 0

5
9 7 7 3 0

0 0 0 0 0

1
0

0

출처: Devin.KR 자체 제작