이진 탐색 트리

바트는 컴퓨터 과학에 관심이 많은 학생이고 여러 가지를 깊이 파고드는 것을 좋아한다. 이번 학기에 자료 구조 수업을 들으면서 이진 탐색 트리가 얼마나 대단한지 알게 되었다.

이진 탐색 트리는 각 정점이 최대 두 개의 자식을 가지는 트리이며, 오른쪽 자식에 저장된 값은 부모에 저장된 값보다 크거나 같고 왼쪽 자식에 저장된 값은 부모에 저장된 값보다 엄격하게 작다는 구조를 유지한다.

그림 1: 이진 탐색 트리

바트는 $a_1, a_2, \ldots, a_n$ 수열이 주어질 때 이 수들이 이진 트리의 어느 깊이에 저장되는지 알고 싶어 한다. 깊이는 해당 정점에서 트리의 가장 위쪽 정점(루트)까지 이동할 때 거치는 정점의 수를 나타낸다.

바트를 도와줄 수 있는가?

첫 번째 줄에 $n$ ($1 \le n \le 10^4$)이 주어진다. 다음 줄에 $n$개의 정수 $a_i$ ($|a_i| < 10^6$)가 주어진다.

$n$개의 수를 출력한다. $i$번째 수는 $a_i$가 저장되는 깊이를 나타낸다.