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

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

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

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

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

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

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

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

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

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

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

#6036 upload 5 done 2 how_to_reg 2

승강기 timer 3s memory 512MB

#6036

승강기 3s 512MB