問題文

$1$から$N$までを1個ずつ含む長さ$N$の数列$A$を用いて二分探索木を構築することを考えます。

数列$A$の$i$番目の要素を$A_i$と書くこととします。 $(1\ \le\ i\ \le\ N)$

二分探索木の構築手順は次のようにします。

• $A_1$を二分探索木の根ノードにします。
• $i\ \ge 2$において$i=2$から$i=N$まで$i$の昇順に$A_i$を次のように二分探索木に配置していきます
  1. 二分探索木の根ノードを着目ノードとします。
  2. 着目ノードの値より$A_i$が小さいとき、着目ノードの左の子が存在する場合は左の子を着目ノードとし、存在しない場合は$A_i$を左の子として配置します。 着目ノードの値より$A_i$が大きいとき、着目ノードの右の子が存在する場合は右の子を着目ノードとし、存在しない場合は$A_i$を右の子として配置します。
  3. $A_i$の配置が決まるまで 2. を繰り返します。

構築完了した二分探索木において、$A_i$が配置されたノードの深さを$B_i$、その子孫数を$C_i$とします。

数列$A$に対応した深さの数列$B$と子孫数の数列$C$を求めてください。

※深さとは、根ノードから対象ノードまでの辺の数を意味します。根ノードの深さは$0$です。

入力

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

1行目に数列$A$の長さ$N$、2行目に数列の各要素$A_i$が空白区切りで入力されます。

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

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

$i\ \neq\ j$ のとき $A_i \neq A_j$ $(1\ \le\ i,j\ \le\ N)$

出力

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

1行目に深さの数列$B$を、2行目に子孫数の数列$C$をそれぞれ空白区切りで出力してください。

サンプル

サンプル1

入力

10
6 2 4 7 5 8 10 1 9 3

出力

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

二分探索木は下図のように構築されます。

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