elevator

题目描述

一座摩天大楼有 $n$ 层。有 $n$ 名乘客在 1 层的电梯里，其中第 $i$ 名乘客的目标楼层为 $a_i$。保证所有 $a_i$ 构成了一个排列。

初始时，第 $i$ 名乘客位于电梯里的第 $i$ 个位置（第一个位置是电梯门口）。

电梯从 1 楼向上运行，并在每层停靠，每层停靠的过程如下：

1. 当电梯到达某乘客的目标楼层时，若该乘客前面（更靠近门）仍有其他乘客，则所有前面的乘客必须暂时离开电梯。
2. 暂时离开的乘客在返回电梯时，可以最优地重新排列他们的顺序，以最小化后续的总出电梯次数。
3. 每次离开电梯（无论是到达目标楼层出站，还是暂时离开）均计为一次出电梯。

请你计算在最优重排策略下，乘客的总出电梯次数。

现在有给定 $q$ 次查询。第 $i$ 次查询前会移除最初位于 $x_i$ 位置的乘客。

你需要输出：

1. 初始状态下（所有 $n$ 名乘客都在）的总出电梯次数。
2. 每次查询后（移除 $x_i$ 乘客，且先前移除的乘客保持不在）的当前乘客集合的总出电梯次数。

输入格式

第一行包含两个非负整数 $n,q$，分别表示人数/楼层数和询问数。

第二行包含 $n$ 个整数 $a_i$，其中 $a_i$ 是第 $i$ 个人想要出电梯的楼层。序列 $(a_i)$ 是一个排列。

第三行包含 $q$ 个整数 $x_i$，表示要移除的初始位置。若 $q=0$，则没有第三行。

输出格式

在一行中，输出 $q+1$ 个整数，其中第 $i$ 个整数是经过 $i-1$ 次询问后（即移除 $i-1$ 个人后）的总出电梯次数。

样例输入

5 2
3 4 1 2 5
3 2

样例输出

9 6 4

数据范围与提示

对于所有数据满足：

• $0 \le q < n \le 10^5$；
• $1 \le a_i \le n$；
• $a_i$ 两两不同；
• $1 \le x_i \le n$；
• $x_i$ 两两不同。