이진 탐색 트리

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 각 노드에는 서로 다른 정수 하나가 저장된다. 어떤 노드에 저장된 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수만 있고 오른쪽 서브트리에는 X보다 큰 수만 있다.

1 이상 N 이하의 정수가 한 번씩 등장하는 수열이 주어진다. 수열의 첫 번째 수를 루트 노드로 두고, 나머지 수를 주어진 순서대로 이진 탐색 트리에 삽입한다. 첫 번째 수를 제외한 각 수 X에 대해 insert(X, root)를 실행하는 것과 같다.

삽입 함수는 다음과 같이 동작한다.

insert(number X, node N)    카운터 C를 1 증가시킨다    if X가 노드 N에 저장된 수보다 작다면        if N의 왼쪽 자식이 없다면            X를 저장한 새 노드를 만들고 N의 왼쪽 자식으로 연결한다        else            insert(X, N의 왼쪽 자식)    else        if N의 오른쪽 자식이 없다면            X를 저장한 새 노드를 만들고 N의 오른쪽 자식으로 연결한다        else            insert(X, N의 오른쪽 자식)

카운터 C는 처음에 0이다. 각 수를 삽입한 직후의 C 값을 출력하라. 루트가 되는 첫 번째 수는 별도의 insert 호출 없이 놓인다.

첫째 줄에 수열의 크기 N이 주어진다. (1 <= N <= 300000)

다음 N개의 줄에는 수열의 수가 순서대로 하나씩 주어진다. 각 수는 1 이상 N 이하의 정수이며, 중복되지 않는다.

N개의 줄을 출력한다. i번째 줄에는 수열의 i번째 수까지 트리에 넣은 직후의 카운터 C 값을 출력한다.