Para un arreglo de enteros $a_1,a_2,\ldots,a_m$, sea $f(a_1,a_2,\ldots,a_m)$ el menor valor posible de

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

entre todos los arreglos de enteros $b_1,b_2,\ldots,b_m$ que cumplen $b_1\le b_2\le\cdots\le b_m$. Los valores $b_i$ pueden ser enteros arbitrarios.

Se te da un arreglo $x_1,x_2,\ldots,x_n$ y una permutación $p_1,p_2,\ldots,p_n$ de los enteros de $1$ a $n$.

Para cada $i$ de $1$ a $n$, considera los índices $p_1,p_2,\ldots,p_i$ ordenados de forma creciente, digamos $q_1<q_2<\cdots<q_i$, y sea $a$ el arreglo $x_{q_1},x_{q_2},\ldots,x_{q_i}$ de longitud $i$. En otras palabras, $a$ está formado por los elementos de $x$ en las primeras $i$ posiciones de la permutación, tomados en el orden en el que aparecen en $x$. Calcula $f(a)$ para cada $i$.

Entrada

La primera línea contiene un único entero $n$ ($1\le n\le 200\,000$): la longitud del arreglo.

La segunda línea contiene $n$ enteros $x_1,x_2,\ldots,x_n$ ($-10^9\le x_i\le 10^9$).

La tercera línea contiene $n$ enteros distintos $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$).

Salida

Imprime $n$ enteros separados por espacios: el $i$-ésimo debe ser el valor de $f(a)$ para el arreglo $a$ construido a partir de $p_1,p_2,\ldots,p_i$.

Ejemplos

Entrada 1

5
5 4 3 2 1
1 2 3 4 5

Salida 1

0 1 2 4 6

Entrada 2

3
3 2 1
1 3 2

Salida 2

0 2 2

Nota

Arreglos del primer ejemplo:

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

Arreglos del segundo ejemplo:

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

Para $[3,1]$, cambiar ambos valores a $1$ (o ambos a $2$, o ambos a $3$) cuesta $2$. Después de insertar el elemento central, cambiar $[3,2,1]$ a $[2,2,2]$ también cuesta $2$.