Elevator Exit Optimization

Problem Description:

There are (n) people in an elevator. The (i)-th person exits at floor (a_i), where (a_{1\sim n}) is a permutation of ({1,2,\ldots,n}). The elevator is a long narrow cabin; initially, the people are arranged in the order of their indices. The elevator stops at floors (1,2,\ldots,n) sequentially from bottom to top.

When a person is about to exit, all the people in front of him (i.e. those with smaller indices in the current order) must temporarily leave the elevator; then they re-enter in an arbitrary order. People behind him are not affected. Whenever a group of people temporarily exits, they always choose the re‐entry order that minimizes the total number of exits (both temporary and permanent).

It can be shown that the minimum total number of exits is equal to the number of people currently in the elevator plus the inversion count of the sequence of exit floors (when considering the people in the order of their original indices). Here the inversion count is defined as the number of pairs ((i,j)) with (i < j) and (a_i > a_j).

Furthermore, you are given (q) operations. In each operation, a person with original index (x_i) is removed from the elevator permanently. You must output the answer for the configuration before any removal and after each removal.

inputFormat

The first line contains two integers (n) and (q).
The second line contains (n) integers (a_1, a_2, \ldots, a_n) representing a permutation of ({1,2,\ldots,n}).
Then (q) lines follow, each containing an integer (x_i) which indicates that the person with original index (x_i) is removed.

outputFormat

Output (q+1) lines. The first line is the answer for the initial configuration, and the (i)-th of the next (q) lines is the answer after the (i)-th removal operation. The answer for any configuration is given by:
[ \text{Answer} = (\text{number of people remaining}) + (\text{inversion count}) ] where the inversion count is the number of pairs ((i,j)) with (i < j) and (a_i > a_j) among the remaining people (ordered by their original indices).

sample

3 1
2 3 1
2

5
3