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 500\,000~
~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