For an array $a_1,a_2,\ldots,a_m$ of integers, let $f(a_1,a_2,\ldots,a_m)$ be the smallest possible value of

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

over all integer arrays $b_1,b_2,\ldots,b_m$ with $b_1\le b_2\le\ldots\le b_m$. The values $b_i$ may be arbitrary integers.

You are given an array $x_1,x_2,\ldots,x_n$ and a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$.

For each $i$ from $1$ to $n$, consider the indices $p_1,p_2,\ldots,p_i$ sorted in increasing order, say $q_1<q_2<\ldots<q_i$, and let $a$ be the array $x_{q_1},x_{q_2},\ldots,x_{q_i}$ of length $i$. In other words, $a$ consists of the elements of $x$ at the first $i$ positions of the permutation, taken in the order in which they occur in $x$. Compute $f(a)$ for every $i$.

Input

The first line contains a single integer $n$ ($1\le n\le 200\,000$): the length of the array.

The second line contains $n$ integers $x_1,x_2,\ldots,x_n$ ($-10^9\le x_i\le 10^9$).

The third line contains $n$ distinct integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$).

Output

Print $n$ integers separated by spaces: the $i$-th of them must be the value of $f(a)$ for the array $a$ built from $p_1,p_2,\ldots,p_i$.

Examples

Input 1

5
5 4 3 2 1
1 2 3 4 5

Output 1

0 1 2 4 6

Input 2

3
3 2 1
1 3 2

Output 2

0 2 2

Note

Arrays in the first example:

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

Arrays in the second example:

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

For $[3,1]$, changing both values to $1$ (or both to $2$, or both to $3$) costs $2$. After the middle element is inserted, changing $[3,2,1]$ to $[2,2,2]$ also costs $2$.