Prepared by: Vito Anić

In this editorial, if we call someone person ~x~, we mean the person who wants to leave at floor ~x~.

If a person wants to get out of the elevator and in front of them there are other people, they will have to go out too. But the best way they can return to the elevator is that they are sorted by the floor on which they want to exit. The closest to the door would be someone who wants to exit soonest.

Let us now solve subtask ~q = 0~.
Observe that we can split people into two groups. People who will exit the elevator just once, and people who will exit the elevator multiple times. For example: 4 5 2 1 6 3 7: people ~1~, ~3~, and ~7~ will exit the elevator once, and the rest of them (~4~, ~5~, ~2~, ~6~) will exit multiple times. We can notice that if someone is the minimum in its suffix, they will exit the elevator only once. To clarify, if one does not have a person who wants to go out before him behind him, there would be no reason for him to exit before he wants to. Because of the way we are retributing people (sorting them) if someone is exiting the elevator multiple times, on the last exit, he will be able to leave without anybody having to exit with him.
Let us now look at the people who exit only once. With them, everyone who wants to leave on a later floor and is in front of them will have to exit when they leave. That can be calculated with Segment or Fenwick tree. When we know that for everyone, the solution will be ~n~ plus that sum.
In the example above, because of ~1~, persons ~4~, ~5~ and ~2~ are forced to exit. Because of ~3~, persons ~4~, ~5~ and ~6~, and nobody because of ~7~. The solution is ~3+3+0+7 = 13~.

Now we know how to solve ~q = 0~. There is one simplification of the calculation above. For calculating the number of people in front of them and leaving on a later floor there is a very nice formula: ~index-value~ (~index~ is the position in the elevator and ~value~ is the floor on which they want to exit). That formula only works for permutations! To clarify why is that correct, if a number is smallest in its suffix, then every number smaller than him is in front of him, which means that there are ~value-1~ smaller numbers in front of him, and the rest are larger.

For the full solution of this task, we need to maintain the property that people in the elevator form a permutation, and somehow be able to the set of people who exit the elevator only once. For the former when erasing some element, using Segment or Fenwick trees we can maintain the values and indices. When erasing a person who exits multiple times, we must reduce the solution by the number of people who exit once are behind them and exit at a smaller floor. When erasing a person who exits the elevator only once, more people can enter that set of people. The easiest way to maintain that set is to calculate offline for every person how long will they be in the set. Total time complexity is ~\mathcal O(n \log n)~.