Problems
Dynamic Inversion
Dynamic Inversion
You are given a permutation {1, 2, 3, ..., n}. Remove m of them one by one, and output the number of inversion pairs before each removal. The number of inversion pairs of an array A is the number of ordered pairs (i, j) such that i < j and Ai
> Aj
.
Input
Contains several test cases. The first line of each case contains two integers n and m (1 ≤ n ≤ 2 * 105
, 1 ≤ m ≤ 105
). After that n lines follow, representing the initial permutation. Then m lines follow, representing the removed integers, in the order of the removals. No integer will be removed twice.
Output
For each removal, output the number of inversion pairs before it.
Explanation
(1, 5, 3, 4, 2) -> (1, 3, 4, 2) -> (3, 4, 2) -> (3, 2) -> (3)
Input example #1
5 4 1 5 3 4 2 5 1 4 2
Output example #1
5 2 2 1