P9910 [COCI 2023/2024 #2] Dizalo

There are $n$ people in an elevator. The $i$-th person gets off at floor $a_i$, and $a_{1\sim n}$ forms a permutation. The elevator is long and narrow, so initially the $n$ people stand in a single line inside the elevator in order of their indices. The elevator goes upward and passes floors $1\sim n$ in increasing order. When someone needs to get off the elevator, everyone in front of them must also get off temporarily, and then they may return to the elevator in any order. People behind them do not need to, and will not, get off the elevator. If the people who temporarily get off always choose the best strategy to decide the order of returning to the elevator each time, find the minimum possible total number of times that all people get off the elevator. You are given $q$ operations. In each operation, a given $x_i$ means removing the person with index $x_i$. You need to output the answer before the first operation and after each operation.

The first line contains two integers $n,q$. The second line contains $n$ numbers $a_{1\sim n}$, guaranteed to form a permutation of $1\sim n$. The third line contains $q$ numbers $x_{1\sim q}$, representing the $q$ queries.

Output one line with $q+1$ numbers, representing the answer before the first operation and the answer after each operation.

### Constraints |$\text{Subtask}$|Score|Special property| |:-:|:-:|:-:| |$1$|$16$|$n,q\le 100$| |$2$|$19$|$n,q\le 1000$| |$3$|$29$|$q=0$| |$4$|$46$|None| For all testdata, $0\le q< n\le 10^5$. Translated by ChatGPT 5