对于整数数组 $a_1,a_2,\ldots,a_m$，定义 $f(a_1,a_2,\ldots,a_m)$ 为在所有满足 $b_1\le b_2\le\cdots\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<\cdots<q_i$，并令 $a$ 为长度为 $i$ 的数组 $x_{q_1},x_{q_2},\ldots,x_{q_i}$。换言之，$a$ 由排列前 $i$ 个位置所指定的 $x$ 中的元素组成，这些元素按照它们在 $x$ 中出现的顺序排列。求出每个 $i$ 对应的 $f(a)$。

输入格式

第一行包含一个整数 $n$（$1\le n\le 200\,000$），表示数组的长度。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$（$-10^9\le x_i\le 10^9$）。

第三行包含 $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]$

第二个样例中的数组：

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

对于 $[3,1]$，将两个值都改为 $1$（或都改为 $2$，或都改为 $3$）的代价为 $2$。插入中间的元素后，将 $[3,2,1]$ 改为 $[2,2,2]$ 的代价也为 $2$。