Gats and the Ceiling Strings

Time limit: 2000 msMemory limit: 256 MB

Gats is exploring a tower of rooms arranged as a rooted tree. Room $1$ is the root. For a room $u$ on the path from room $1$ to room $v$ , room $u$ is called an ancestor of room $v$ ; room $v$ is also its own ancestor.

There is a dangling string in every room. The string in room $i$ has length $A_i$ .

For each room $v$ , Gats has a threshold $B_v$ and a reach limit $R_v$ . A string in an ancestor room $u$ is usable from room if both conditions hold:

$A_u \ge B_v$ .
The number of edges on the path from room $v$ to room $u$ is at most .

Among all usable strings from room $v$ , Gats chooses one with the smallest number of edges from room $v$ . For every room, determine this smallest number. If no usable string exists, the answer for that room is $-1$ .

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of rooms.

The second line contains $N$ integers (), where is the length of the string in room .

Output

Print one line containing $N$ integers $C_1, C_2, \ldots, C_N$ separated by spaces. For each with , must be the smallest number of edges from room to a usable string, or if no usable string exists.

Samples

Sample 1

Input

Output

0 -1 0 -1 1

In the first sample, rooms $1$ and $3$ can use their own strings, so their answers are $0$ . Room $5$ uses the string in room $3$ , which is $1$ edge above it. Rooms and have no usable string within their reach limits.

Gats and the Ceiling Strings

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2