Dynamic Inversion
Very easy
Execution time limit is 1 second
Runtime memory usage limit is 122.174 megabytes
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]
.
Input
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.
Output
For each removal, output the number of inversion pairs before it.
Examples
Input #1
Answer #1
Note
(1, 5, 3, 4, 2) -> (1, 3, 4, 2) -> (3, 4, 2) -> (3, 2) -> (3)
Submissions 255
Acceptance rate 26%