페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6036

승강기 3초 512MB

문제

n층으로 이루어진 빌딩이 있으며 n명의 사람들이 승강기에 있다.

i번째 사람은 a_i층으로 가고 싶어한다. 동일한 층으로 가고 싶은 경우는 없다. 즉, 모든 a_i는 서로 다르다.

빌딩에는 모든 사람이 들어갈 수 있는 큰 승강기가 있지만 특이한 구조로 되어 있는데, 줄을 서는 것과 같이 일렬로 들어가야 하며, 나란히 서 있을 수 없는 구조이다.

위 그림은 첫 번째 예제의 시작 상태이며 승강기 내부에 있는 사람들을 표현한 것이다. 승강기는 1층에 있으며, 3번째에 있는 사람이 나가야 하는 상황이다. 따라서 1번째와 2번째에 있는 사람이 잠시 나가주어야 3번째 사람이 나갈 수 있다.

모든 사람이 승강기에 탑승했지만, 내리는 순서를 고려하지 않고 막무가내로 탑승하였다.

i번째 사람은 승강기 내부 문 앞 기준으로 i번째로 줄을 서 있는 사람을 말하며, i번째 사람이 나가려면 그 앞에 있는 사람들이 일시적으로 모두 나가야 내릴 수 있다. 승강기로 돌아올 때는 원하는 대로 순서를 변경할 수 있다. 내리려는 사람 뒤에 있는(문에서 더 먼) 사람은 엘리베이터에서 내리지 않는다.

승강기는 항상 1층에서 n층으로 이동하는데 사람들이 내리고 다시 탈 때 항상 최적의 순서로 탑승한다면, 승강기에서 얼마나 많이 내렸는지 알고 싶어졌다.

내린 횟수가 궁금하기에 한 명이 여러 번 내려도 여러 번 센다.

그러나 단순하게 내린 횟수를 구하는 문제는 너무 쉽기에 q개의 질문이 들어오면 답을 하는 문제로 바꾸었다.

만약 x_i번째 사람이 승강기에 없다면, 내린 횟수는 몇 번인가?

(이전 질문으로 인해 없어진 사람은 다시 들어오지 않으며 다음 질문에 영향을 준다)


입력

첫 번째 줄에 두 개의 음이 아닌 정수 n, q (0 \le q \lt n \le 10^5), 사람/층 수와 질문 수가 주어진다.

두 번째 줄에 n개의 정수 a_i(1 \le a_i \le n, i \neq j 일 때 a_i \neq a_j), 즉 각 사람이 승강기에서 내리고자 하는 층이 주어진다.

세 번째 줄에는 q개의 정수 x_i1 \le x_i \le n, i \neq j 일 때 x_i \neq x_j) 질문이 주어진다.


출력

q+1개의 수를 공백을 구분으로 한 줄로 출력한다.


부분문제

번호 점수 조건
#116점

n,q \le 100

#219점

n,q \le 1000

#329점

q=0

#436점

추가 제약 조건 없음.


예제1

입력
52
34125
32
출력
964

첫 번째 예제의 초기 상태의 답이 9인 이유를 설명하고 있다.

1층에서는 3번째 있는 사람이 나가기 위해 1,2번째에 있는 사람이 나가야 한다. (3회)

2층에서는 4번째 있는 사람이 나가기 위해 1,2번째에 있는 사람이 나가야 한다. (3회)

3층에서는 1번째 있는 사람이 나가기 위해 나가야 하는 사람은 없다. (1회)

4층에서는 2번째 있는 사람이 나가기 위해 나가야 하는 사람은 없다. (1회)

5층에서는 5번째 있는 사람이 나가기 위해 나가야 하는 사람은 없다. (1회)

따라서 총 나가는 횟수는 3 + 1 + 1 +1 = 9회 나가게 된다.


예제2

입력
70
4521637
출력
13

예제3

입력
32
312
12
출력
521

출처

COCI 2023/2024 Contest #2 3번

역링크