다음에 만날 인기 메뉴

문제

한 학교의 급식실은 N일짜리 메뉴표를 만들고, 마지막 날이 지나면 첫날부터 같은 메뉴표를 반복해서 사용한다. 메뉴표의 각 날에는 학생들이 정한 인기도 점수가 하나씩 붙어 있다. 점수는 0 이상 9 이하의 정수이며, 서로 다른 날의 점수가 같을 수도 있다. 급식 담당자는 각 날의 메뉴 옆에 지금보다 인기 있는 메뉴를 다시 만나기까지 기다려야 하는 날짜 수를 표시하려 한다. 어떤 날의 점수가 x라면, 바로 다음 날부터 메뉴표의 진행 방향으로 하루씩 이동하며 점수를 확인한다. 점수가 x보다 엄격히 큰 날을 처음 만났을 때 이동한 날짜 수가 그날의 대기 일수다. 점수가 같은 날은 조건을 만족하지 않으므로 계속 이동한다. 메뉴표의 마지막 날 다음에는 첫날이 오며, 이 경계를 넘을 때도 하루가 지난 것으로 센다. 따라서 마지막 날에서도 첫날이나 그 뒤의 날이 정답이 될 수 있다. 확인하는 범위는 출발한 날을 제외한 나머지 N-1일이다. 이 범위에 더 높은 점수의 날이 없다면 대기 일수를 -1로 정한다. 같은 메뉴표가 계속 반복되므로 한 바퀴 안에서 찾지 못한 점수를 더 오래 기다린다고 새롭게 찾을 수는 없다. 특히 메뉴표가 하루뿐이면 비교할 다른 날이 없으므로 그날의 답은 -1이다. 예를 들어 점수가 3인 날에서 다음 날의 점수가 3이고 그다음 날의 점수가 7이라면 대기 일수는 2다. 더 높은 점수가 여러 번 나타나더라도 점수가 가장 높은 날을 고르는 것이 아니라 진행 방향으로 가장 먼저 만나는 날을 고른다. 각 날의 답은 다른 날의 답과 독립적으로 계산하며, 어떤 날을 찾았다고 해서 메뉴표에서 제거하지 않는다. 첫날부터 마지막 날까지 모든 날의 대기 일수를 순서대로 구한다.

입력

첫째 줄에 메뉴표의 일수 N이 주어진다. 둘째 줄에 첫날부터 마지막 날까지의 인기도 점수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1 ≤ N ≤ 190,000, 0 ≤ A_i ≤ 9다.

출력

첫째 줄에 각 날의 대기 일수를 첫날부터 순서대로 공백으로 구분하여 출력한다. 조건을 만족하는 다른 날이 없으면 해당 위치에 -1을 출력한다.

5
2 2 5 1 4

2 1 -1 1 3

4
6 6 6 6

-1 -1 -1 -1

출처: Devin.KR 자체 제작