정수 배열 $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$라고 하자. 길이가 $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$)이 주어진다.

두 번째 줄에 $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$이다.