Binary Search Tree

Interview

Time limit2sMemory limit512 MB

Summary

Insert a sequence of integers into a BST and output the depth of each inserted node.

Level: Easy3 of 10
Topics: Tree, Recursion, Simulation
Solved: No attempts yet

Problem

Bat is a student with a strong interest in computer science, and he likes to dig deep into many subjects. This semester he is taking a data structures course, and he has come to understand how remarkable binary search trees are.

A binary search tree is a tree in which every vertex has at most two children, and it maintains the structure that the value stored in the right child is greater than or equal to the value stored in the parent, while the value stored in the left child is strictly less than the value stored in the parent.

Illustration 1: A binary search tree

Given a sequence $a_1, a_2, \ldots, a_n$ , Bat wants to know at which depth of the binary tree these numbers are stored. Depth means the number of vertices passed through when moving from that vertex up to the topmost vertex of the tree (the root).

Can you help Bat?

Input

The first line contains $n$ ( $1 \le n \le 10^4$ ). The next line contains $n$ integers $a_i$ ( $|a_i| < 10^6$ ).

Output

Output $n$ numbers. The $i$ -th number is the depth at which $a_i$ is stored.

Examples2

Example 1

Input

9
8 10 3 1 6 14 4 13 7

Expected output

0 1 1 2 2 2 3 3 3

Example 2
Input
```
4
-1 0 1 1
```
Expected output
```
0 1 2 3
```