整数の配列 $a_1, a_2, \ldots, a_m$ に対して、$f(a_1, a_2, \ldots, a_m)$ を、$b_1 \le b_2 \le \ldots \le b_m$ を満たすすべての整数配列 $b_1, b_2, \ldots, b_m$ にわたる

$$ \sum_{i=1}^{m} |a_i-b_i| $$

の最小値とします。$b_i$ の値は任意の整数でかまいません。

配列 $x_1, x_2, \ldots, x_n$ と、$1$ から $n$ までの整数の順列 $p_1, p_2, \ldots, p_n$ が与えられます。

$1$ から $n$ までの各 $i$ について、添字 $p_1, p_2, \ldots, p_i$ を昇順に並べたものを $q_1 < q_2 < \ldots < q_i$ とし、長さ $i$ の配列 $x_{q_1}, x_{q_2}, \ldots, x_{q_i}$ を $a$ とします。言い換えると、$a$ は、順列の先頭 $i$ 個の位置にある値を添字とする $x$ の要素を、$x$ に現れる順に並べたものです。すべての $i$ について $f(a)$ を求めてください。

入力

最初の行には、配列の長さを表す整数 $n$（$1 \le n \le 200\,000$）が $1$ 個与えられます。

$2$ 行目には、$n$ 個の整数 $x_1, x_2, \ldots, x_n$（$-10^9 \le x_i \le 10^9$）が与えられます。

$3$ 行目には、$n$ 個の相異なる整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）が与えられます。

出力

$n$ 個の整数を空白区切りで出力してください。その $i$ 番目は、$p_1, p_2, \ldots, p_i$ から構成した配列 $a$ に対する $f(a)$ の値でなければなりません。

入出力例

入力 1

5
5 4 3 2 1
1 2 3 4 5

出力 1

0 1 2 4 6

入力 2

3
3 2 1
1 3 2

出力 2

0 2 2

注記

最初の例における配列は次のとおりです。

• $[5], [5, 4], [5, 4, 3], [5, 4, 3, 2], [5, 4, 3, 2, 1]$

$2$ 番目の例における配列は次のとおりです。

• $[3], [3, 1], [3, 2, 1]$

$[3, 1]$ に対して、両方の値を $1$（または両方を $2$、または両方を $3$）に変更するコストは $2$ です。中央の要素が挿入された後、$[3, 2, 1]$ を $[2, 2, 2]$ に変更するコストも $2$ です。