P3149 Sorting

There are $n$ people standing in front of Xiao A in order. Xiao A will perform $m$ operations on these $n$ people, one after another. In each operation, choose a position $k$. Take out from the line all people whose heights are less than or equal to the height of the person currently at position $k$. Then, sort these extracted people by height in increasing order (from shortest to tallest), and put them back into the line at the same set of positions they originally occupied, filling those positions from left to right. Xiao A is interested in the number of inversions of the sequence formed by these $n$ heights. Now Xiao A wants to know the inversion count of this sequence after each operation. ---- Update (2021-01-17): In the $a$ sequence, an inversion is a pair $(i, j)$ such that $i < j$ and $a_i > a_j$.

The first line contains two integers $n$ and $m$, the number of people and the number of operations. The next line contains $n$ integers $a_i$, representing the heights from left to right in the initial state. Each of the next $m$ lines contains one integer, the $k$ for that operation.

Output $m + 1$ lines. The first line is the number of inversions before any operation. For $i \ge 2$, line $i$ is the inversion count after the $(i - 1)$-th operation.

[Sample Explanation #1] After the first operation, the sequence is $1, 5, 2, 4, 3$. After the second operation, the sequence is $1, 5, 2, 3, 4$. Constraints For $100 \%$ of the testdata, $1 \le n,m \le 3 \times 10^5$, $1 \le k \le n$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5