For her current programming project, Soriya needs to first construct the array which has length
. However, to entertain herself, she decides to add the elements in the order described by the permutation
. That is, for her
th insertion, she will add the element
to its position in the array. Since Soriya has nothing better to do with her life, she wonders: how many inversions will the array
have after each insertion? An inversion is a pair of indices
such that
and
.
Input Specification
The first line contains the positive integer .
The second line consists of positive integers, the array
.
The third line consists of positive integers, the permutation
.
Output Specification
Output lines, the
th of which containing a single integer, the number of inversions after Soriya adds her
th element.
Constraints
In all subtasks,
Subtask 1 [15%]
for
Subtask 2 [25%]
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
Comments