For her current programming project, Soriya needs to first construct the array $a$ which has length $N$. However, to entertain herself, she decides to add the elements in the order described by the permutation $p$. That is, for her $i$th insertion, she will add the element $a_{p_i}$ to its position in the array. Since Soriya has nothing better to do with her life, she wonders: how many inversions will the array $a$ have after each insertion? An inversion is a pair of indices $(i,j)$ such that $1\le i<j\le N$ and $a_i>a_j$.

Input Specification

The first line contains the positive integer $N$.
The second line consists of $N$ positive integers, the array $a_1,a_2,\dots ,a_N$.
The third line consists of $N$ positive integers, the permutation $p_1,p_2,\dots ,p_N$.

Output Specification

Output $N$ lines, the $i$th of which containing a single integer, the number of inversions after Soriya adds her $i$th element.

Constraints

In all subtasks,
$1\le N\le 500000$
$1\le a_i,p_i\le N$

Subtask 1 [15%]

$p_i=i$ for $1\le i\le N$

Subtask 2 [25%]

$1\le a_i\le 2$

Subtask 3 [60%]

No additional constraints.

Sample Input 1

5
4 3 1 2 3
1 2 3 4 5

Sample Output 1

0
1
3
5
6

Sample Input 2

5
4 3 1 2 3
3 5 1 4 2

Sample Output 2

0
0
2
3
6