BOJ 14057 Towers

문제 링크:

문제 내용

높이가 모두 다른 $N$채의 빌딩들이 좌우로 일렬로 서 있고 그 사이 어느 한 곳에 탑을 지으려고 합니다. 두 빌딩의 사이, 맨 왼쪽 빌딩보다 왼쪽, 맨 오른쪽 빌딩보다 오른쪽에 짓는 것 모두 가능하고, 탑의 높이도 모든 빌딩의 높이와 다릅니다.

$i$번째 빌딩이 탑보다 왼쪽에 있고, 그 높이가 탑보다 낮으며, $i$번째 빌딩과 탑 사이에 $i$번째 빌딩보다 높은 빌딩이 없으면, $i$번째 빌딩이 “탑에서 잘 보인다"고 말합니다. 지으려는 탑의 높이가 주어졌을 때, “탑에서 잘 보이는” 빌딩의 최대 개수를 구하는 쿼리를 $K$번 수행하세요.

입력

첫째 줄에는 빌딩의 개수 $N$과 쿼리의 개수 $K$가 주어집니다. $(1 \le N \le 10^6,\ 1 \le K \le 10^5)$

둘째 줄에는 $1$ 이상 $10^9$ 이하의 정수 $N$개가 주어지며, 빌딩들의 높이를 나타냅니다.

셋째 줄에는 $1$ 이상 $10^9$ 이하의 정수 $K$개가 주어지며, 각 쿼리에서 지으려는 탑의 높이를 나타냅니다.

출력

입력과 같은 순서로 각 쿼리의 답을 한 줄에 공백으로 구분해서 출력합니다.

문제 풀이