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 A[i]
> A[j]
.
Contains several test cases. The first line of each case contains two integers n and m (1 ≤ n ≤ 2 * 10^5
, 1 ≤ m ≤ 10^5
). 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.
For each removal, output the number of inversion pairs before it.
(1, 5, 3, 4, 2) -> (1, 3, 4, 2) -> (3, 4, 2) -> (3, 2) -> (3)