题目描述

译自 COCI 2023/2024 Contest #2 T3「Dizalo」

在某个城市中有一座 $n$ 层高的摩天大楼。有 $n$ 个人正在一层等电梯。第 $i$ 个人想要到 $a_i$ 层去。没有两个人想到相同的楼层去。

这座摩天楼有一部足以让所有人乘坐的电梯，但是它太窄了以至于两个人不能并排站，他们必须一个人站在另一个人的后面。

所有人都上了电梯，但是他们没考虑下梯的顺序！最初，从电梯门的方向看，第 $i$ 个人站在位置 $i$。如果一个人想要下电梯，在他之前（离门更近）的所有人都必须也暂时离开电梯。当返回电梯时，他们可以任意重新排列站的位置。站在希望下梯的人后面（离门更远）的人不会离开电梯。

上图展示了在第一个样例中电梯中的人开始时的状态。电梯在一楼，站在位置 $3$ 的人想要下梯。为了他下梯，站在位置 $1$ 和位置 $2$ 的人也必须离开电梯。

Mirko 正在观察和思考他们所处的情况。他想知道如果人们总是以最优顺序返回电梯的话，会有多少次离开电梯的事件发生。如果一个人多次离开电梯，那么每次都分别计数。

Mirko 是一个经验丰富的编程者，它可以十分轻松地解决这个问题。但他的开心是短暂的，因为他旁边的人是他的朋友 Slavko。Slavko 想到了 $q$ 个问题：如果在位置 $x_i$ 的人不在电梯里，会有多少次离开电梯的事件发生？

Mirko 对 Slavko 的第一个问题之前和每个问题之后的回答都很感兴趣。注意对于每个问题，之前问题中的所有人都不被认为在电梯中。Mirko 开始解决问题，但他很快意识到，即使对他来说，这也不是一件容易的事。请帮助他解决这个问题！

注意：电梯总会从一楼移动到 $n$ 楼，并在某人希望下梯的楼层停。

输入格式

第一行包含两个非负整数 $n$ 和 $q\ (0\le q<n\le 10^5)$，表示人（楼层）数和问题数。

第二行包含 $n$ 个整数 $a_i\ (1\le a_i\le n,a_i\neq a_j, i\neq j)$，其中 $a_i$ 表示第 $i$ 个人希望下梯的楼层。序列 $(a_i)$ 是一个排列。

第三行包含 $q$ 个整数 $x_i\ (1\le x_i\le n,x_i\neq x_j,i\neq j)$，表示 Slavko 的问题。

输出格式

输出一行 $q+1$ 个整数，第 $i$ 个整数表示在 $i-1$ 个问题后离开电梯事件的发生次数。

5 2
3 4 1 2 5
3 2

9 6 4

下图展示了在第一个询问之前离开电梯事件的发生过程。

电梯在一楼，站在位置 $3$ 的人想要下梯。但为了他下梯，站在位置 $1$ 和位置 $2$ 的人也必须离开电梯，然后他们以相同的位置返回电梯。

在此之后，在二楼，站在位置 $4$ 的人想要下梯。再次，站在位置 $1$ 和位置 $2$ 的人也必须离开电梯，然后他们以相同的位置返回电梯。

在此之后，在三楼，站在位置 $1$ 的人下梯，不会使得其他人离开电梯。

在此之后，在四楼，站在位置 $2$ 的人下梯，不会使得其他人离开电梯。

在此之后，在四楼，站在位置 $5$ 的人下梯。

总共有 $3+3+1+1+1=9$ 次离开电梯事件发生。

7 0
4 5 2 1 6 3 7

13

3 2
3 1 2
1 2

5 2 1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n,q\le 100$	$15$
$2$	$n,q\le 1\ 000$	$17$
$3$	$q=0$	$26$
$4$	无附加限制	$42$