엘리베이터

도시에 $n$층짜리 높은 빌딩이 있다. 1층 승강장에는 $n$명의 사람이 엘리베이터를 기다리고 있다. $i$번째 사람은 $a_i$층에서 내리려고 한다. 같은 층에서 내리려는 사람은 둘이 없다.

빌딩에는 엘리베이터가 한 대 있다. 모든 사람이 탈 만큼 크지만 너무 좁아서, 두 사람이 나란히 설 수 없고 앞뒤로 줄을 서야 한다.

모든 사람이 엘리베이터에 탔지만, 내리는 순서는 아무도 생각하지 않았다. 어떤 사람이 내리려면 문에 더 가까이 있는 앞쪽 사람들이 모두 잠시 내려야 한다. 다시 탈 때는 원하는 대로 순서를 바꿀 수 있다. 내리려는 사람보다 뒤(문에서 먼 쪽)에 있는 사람은 내리지 않는다.

위 그림은 첫 번째 예제에서 사람들이 처음 서 있는 순서를 보여준다. 엘리베이터는 1층에 있고, 3번 위치의 사람이 내리려고 한다. 그 사람이 내리려면 1번과 2번 위치의 사람이 먼저 내려야 한다.

미르코는 이 상황을 보고, 엘리베이터에 다시 타는 사람들이 항상 최적으로 순서를 정한다면 내리는 횟수가 몇 번인지 생각한다. 한 사람이 여러 번 내리면 내릴 때마다 따로 센다.

미르코에게는 이 문제가 쉽지만, 친구 슬라브코가 $q$개의 질문을 했다. 각 질문은 다음과 같다. 위치 $x_i$의 사람이 엘리베이터에 없다면 내리는 횟수는 몇 번인가? 미르코는 첫 질문 전과 매 질문 후의 답을 알고 싶어 한다. 각 질문마다 이전 질문에서 빠진 사람들도 계속 엘리베이터에 없는 것으로 본다.

엘리베이터는 항상 1층에서 $n$층까지 움직이며, 누군가 내리려는 층마다 멈춘다.

첫 줄에 두 개의 음이 아닌 정수 $n$과 $q$ ($0 \le q < n \le 10^5$)가 주어진다. 각각 사람(층)의 수와 질문의 수이다.

둘째 줄에는 $n$개의 정수 $a_i$ ($1 \le a_i \le n$, $i \ne j$이면 $a_i \ne a_j$)가 주어진다. $a_i$는 $i$번째 사람이 내리려는 층이다. 수열 $(a_i)$는 순열이다.

셋째 줄에는 $q$개의 정수 $x_i$ ($1 \le x_i \le n$, $i \ne j$이면 $x_i \ne x_j$)가 주어진다. 슬라브코가 낸 질문이다.

한 줄에 $q+1$개의 수를 출력한다. $i$번째 수는 $i-1$개의 질문을 처리한 뒤의 내리는 횟수이다.

이 그림은 첫 질문 전의 내리는 과정을 보여준다. 엘리베이터는 1층에 있고, 3번 위치의 사람이 내리려고 한다. 그러려면 1번과 2번 위치의 사람이 먼저 내려야 하고, 이들은 같은 위치로 돌아온다.

그다음 2층에서는 4번 위치의 사람이 내리려고 한다. 이번에도 1번과 2번 위치의 사람이 먼저 내리고, 같은 위치로 돌아온다.

3층에서는 1번 위치의 사람이 다른 사람을 내리게 하지 않고 내린다.

4층에서는 2번 위치의 사람이 다른 사람을 내리게 하지 않고 내린다.

마지막으로 5층에서는 5번 위치의 사람이 내린다.

총 내리는 횟수는 3 + 3 + 1 + 1 + 1 = 9이다.