28400번 - 거대 로봇 전투

학원 도시 소녀들의 우정과 사랑, 감동의 밀리터리 액션!

블루 아카이브는 2021년 11월 9일에 출시한 수집형 롤플레잉 게임이다. 블루 아카이브에서는 플레이어가 선생님이 되어 최대 6명의 학생과 함께 PvP, PvE 미션에 참여할 수 있다. 플레이어는 학생에게 특수 스킬을 사용하도록 하여 전략적으로 미션을 수행할 수 있다. 게임 플레이뿐만 아니라 다양한 문제를 해결하는 스토리, 개발사와 유저 간의 활발한 소통으로 2022년 대한민국 게임대상 인기게임상 부문을 수상했다.

거대 로봇과 미니언이 대치하고 있는 모습의 그림이다.

여러분은 선생님이 되어 학생들을 지휘하여 페로로 미니언을 소탕하려고 한다. 학생들은 KAITEN FX Mk.U라는 거대 로봇에 탑승해 임무를 수행한다. 거대 로봇은 제일 왼쪽에 있는 미니언보다 왼쪽에서 임무를 시작하며, 왼쪽으로부터 $i$ $(1\le i\le N)$번째 미니언의 키는 $H_i$이고, 거대 로봇의 키는 임무를 시작하기 전에 선생님이 조절할 수 있다. 거대 로봇은 자신이 볼 수 있는 미니언 중 하나를 골라 공격할 수 있다. 거대 로봇이 $i$번째 미니언을 볼 수 있으려면, $i$번째 미니언 왼쪽에 있는 모든 미니언이 거대 로봇보다 키가 작아야 한다. 거대 로봇이 미니언을 공격하면 해당 미니언은 완전히 사라지며 다른 미니언의 위치나 키는 변하지 않는다.

거대 로봇을 볼 수 있는 미니언들 또한 거대 로봇을 공격한다. $i$번째 미니언이 거대 로봇을 볼 수 있으려면, $i$번째 미니언 왼쪽에 있는 모든 미니언이 $i$번째 미니언보다 키가 작아야 한다. 여러분은 미니언의 공격을 버틸 수 있도록 내구도가 높은 거대 로봇을 준비해야 한다. 내구도가 $K$인 거대 로봇으로 임무를 완수하려면 임무 시작부터 끝까지 한 번이라도 $K$마리보다 많은 미니언이 거대 로봇을 동시에 공격하면 안 된다.

여러분은 학생들이 타는 거대 로봇의 키에 따라 필요한 내구도가 다르다는 것을 파악했다. 거대 로봇의 키 $Q$개가 주어지면 임무를 완수하기 위해 필요한 로봇의 최소 내구도를 구하는 프로그램을 작성하여라.

첫 번째 줄에 미니언의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(1\le N,Q\le 250\, 000)$

두 번째 줄에는 각 미니언의 키 $H_i$가 공백으로 구분되어 주어진다. $(1\le H_i\le 10^9)$

세 번째 줄부터 $Q$개의 줄에는 학생들이 타는 거대 로봇의 키 $B_j$가 주어진다. $(1\le B_j\le 10^9)$

입력받는 모든 값은 정수이다.

$Q$개의 줄에 걸쳐 거대 로봇의 키가 $B_j$일 경우 학생들이 임무를 완수하기 위해 필요한 거대 로봇의 최소 내구도를 출력한다.