Given a rooted tree $T$ with root $1$, where the children of each node have a left-to-right order. Initially, $T$ contains only node $1$.

There are $n$ operations. In the $i$-th operation, you are given $f_i$, and you must create a new node $i+1$ as the rightmost child of $f_i$, adding it to the tree $T$. After each operation, you need to answer the following question:

For a tree, define the "Trink transformation" as follows:

• Simultaneously consider all nodes $u$ (where $u \neq 1$). If $u$ is not the first child (from left to right) of its parent, change the parent of $u$ to be the rightmost sibling among all siblings to the left of $u$.

Find the minimum number of Trink transformations required such that, after performing these transformations on $T$, applying one more Trink transformation to the resulting tree leaves its structure unchanged.

The queries are independent. That is, the Trink transformations are not actually applied to the original tree.

Input

The first line contains an integer $n$ ($1 \leq n \leq 10^6$).

The second line contains $n$ integers, representing $f_1, \ldots, f_n$ ($1 \leq f_i \leq i$) in order.

Output

Output $n$ lines, where the $i$-th line contains an integer representing the answer after the $i$-th operation.

Examples

Input 1

5
1 1 2 2 5

Output 1

0
1
2
3
4

Note

For the last query, the following shows the structure of tree $T$ after $k$ ($0 \leq k \leq 4$) operations: