아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

탑

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 방문객은 아래층부터 계단을 순서대로 오르며 키보다 높거나 같은 계단 앞에서 멈추고 도달한 최고 층을 기록합니다.
난이도

보통10점 중 5점

유형
이분 탐색, 누적 합
정답자
아직 제출이 없습니다

문제

바이트랜드에 높은 탑이 세워졌습니다. 탑으로 오르는 계단은 nn개의 칸으로 이루어져 있고, 각 계단 칸에는 고유한 높이가 정해져 있습니다.

mm명의 주민이 이 탑을 방문하려고 합니다. 각 주민은 키를 가지고 있으며, 이 키로 계단을 한 칸씩 올라갑니다. 어떤 주민이 특정 계단 칸에 올라서려면 그 주민의 키가 그 칸의 높이보다 엄격히 커야 합니다(키와 칸의 높이가 같으면 올라설 수 없습니다). 어떤 칸을 넘지 못하면 주민은 그 자리에서 멈추고, 더 위로는 올라갈 수 없습니다.

주민은 항상 맨 아래 11번째 계단부터 위로 순서대로 올라갑니다. 각 계단 칸의 높이와 방문하는 주민들의 키가 주어질 때, 각 주민이 어느 계단 칸까지 올라갈 수 있는지 구하세요.

입력

첫째 줄에 두 정수 nn, mm (1≤n,m≤5000001 \le n, m \le 500000)이 주어집니다. 각각 탑으로 오르는 계단 칸의 수와 탑을 방문하려는 주민의 수를 뜻합니다.

둘째 줄에는 nn개의 정수 a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \le a_i \le 10^9)이 주어지며, aia_i는 ii번째 계단 칸의 높이입니다. 11번째 칸이 탑의 맨 아래에 있고, 이어지는 칸은 순서대로 한 칸씩 위에 있습니다.

셋째 줄에는 mm개의 정수 b1,b2,…,bmb_1, b_2, \dots, b_m (1≤bi≤1091 \le b_i \le 10^9)이 주어지며, bib_i는 ii번째 주민의 키입니다.

출력

한 줄에 mm개의 정수 w1,w2,…,wmw_1, w_2, \dots, w_m을 공백으로 구분해 출력합니다. wiw_i는 ii번째 주민이 올라갈 수 있는 가장 높은 계단 칸의 번호입니다. 주민이 11번째 칸조차 올라서지 못하면 wi=0w_i = 0입니다.

예제1

  1. 예제 1

    입력
    3 6
    2 5 1
    1 2 3 4 5 6
    
    예상 출력
    0 0 1 1 1 3