Problem Statement

Consider building a binary search tree using a sequence $A$ of length $N$ that contains each of $1$ through $N$ exactly once.

Let $A_i$ denote the $i$-th element of the sequence $A$. $(1\ \le\ i\ \le\ N)$

The binary search tree is built by the following procedure.

• Make $A_1$ the root node of the binary search tree.
• For $i\ \ge 2$, place $A_i$ into the binary search tree in ascending order of $i$, from $i=2$ to $i=N$, as follows:
  1. Let the root node of the binary search tree be the current node.
  2. If $A_i$ is smaller than the value of the current node: if the current node has a left child, make the left child the current node; otherwise, place $A_i$ as its left child. If $A_i$ is larger than the value of the current node: if the current node has a right child, make the right child the current node; otherwise, place $A_i$ as its right child.
  3. Repeat 2. until the position of $A_i$ is determined.

In the completed binary search tree, let $B_i$ be the depth of the node where $A_i$ is placed, and let $C_i$ be its number of descendants.

Find the sequence $B$ of depths and the sequence $C$ of descendant counts corresponding to the sequence $A$.

* The depth of a node is the number of edges from the root node to that node. The depth of the root node is $0$.

Input

$N$
$A_1\ A_2\ A_3\ \dots\ A_{N-1}\ A_N$

The first line contains the length $N$ of the sequence $A$, and the second line contains the elements $A_i$ of the sequence, separated by spaces.

$10\ \le\ N\ \le\ 200000=2\ \times\ 10^{5}$

$1\ \le\ A_i\ \le\ N$ $(1\ \le\ i\ \le\ N)$

$A_i \neq A_j$ if $i\ \neq\ j$ $(1\ \le\ i,j\ \le\ N)$

Output

$B_1\ B_2\ B_3\ \dots\ B_{N-1}\ B_N$
$C_1\ C_2\ C_3\ \dots\ C_{N-1}\ C_N$

Print the sequence $B$ of depths on the first line and the sequence $C$ of descendant counts on the second line, each separated by spaces.

Sample

Sample 1

Input

10
6 2 4 7 5 8 10 1 9 3

Output

0 1 2 1 3 2 3 2 4 3
9 4 2 3 0 2 1 0 0 0

The binary search tree is built as shown in the figure below.

10
10 9 8 7 6 5 4 3 2 1

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

10
5 6 4 7 3 8 2 9 1 10

0 1 1 2 2 3 3 4 4 5
9 4 3 3 2 2 1 1 0 0

20
10 7 4 9 16 6 13 15 18 17 3 8 2 20 19 14 12 5 1 11

0 1 2 2 1 3 2 3 2 3 3 3 4 3 4 4 3 4 5 4
19 8 5 1 9 1 4 1 3 0 2 0 1 1 0 0 1 0 0 0

20
10 5 15 3 7 13 17 1 4 6 9 11 14 16 19 2 8 12 18 20

0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4
19 8 9 3 3 3 4 1 0 0 1 1 0 0 2 0 0 0 0 0