체인

N개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. 각 원소 $a_k$ ($k = 1, 2, \ldots, n$)에 대해, $a_k$보다 크면서 $a_k$의 오른쪽에 있는 첫 번째 원소를 찾는다(존재하는 경우). 이를 $a_{k1}$이라 하자. 그런 다음 $a_{k1}$에 대해 같은 과정을 반복해 $a_{k2}$를 찾고, 수열이 끝날 때까지 이어간다. 이렇게 만들어진 부분 수열 $a_{k1}, a_{k2}, \ldots$를 인덱스 $k$에서 시작하는 체인이라 부른다.

프로그램 chain을 작성하여, 각 인덱스 $k$에서 시작하는 체인의 길이를 출력하라.

표준 입력의 첫째 줄에 $N$이 주어진다. 둘째 줄에 주어진 수열의 원소들이 공백으로 구분되어 주어진다.

표준 출력의 한 줄에, 입력 데이터의 각 원소에 대응하는 체인의 길이를 출력한다. 연속하는 두 수는 공백 하나로 구분한다.

• $0 < N < 500\,000$
• $0 < a_i < 1\,000\,000$, $i = 1, \ldots, N$