편의점 교환권으로 고를 수 있는 상품

문제

동네 편의점에서 행사 상품을 진열하고 교환권을 나누어 주었다. 행사 상품의 종류는 N개이며, 각 종류에는 정수로 표시된 교환 가격이 붙어 있다. 여기에서 가격의 단위는 행사 전용 단위이며 실제 화폐 단위와는 관계가 없다. 상품 종류마다 가격이 하나씩 정해져 있지만, 서로 다른 종류의 가격이 같을 수 있다. 가격이 같아도 진열된 종류가 다르면 선택 가능한 상품을 셀 때 각각 하나로 센다. 각 교환권에는 사용할 수 있는 금액이 정수로 적혀 있다. 손님은 교환권 한 장을 사용하여 그 금액 이하의 가격이 붙은 행사 상품 중 정확히 한 종류를 고를 수 있다. 상품의 가격이 교환권 금액과 같아도 선택할 수 있다. 상품을 고른 뒤 금액이 남더라도 다른 상품을 추가로 고르거나 남은 금액을 다음 교환권에 더할 수는 없다. 여러 종류의 가격을 합쳐서 교환권 금액과 비교하지도 않는다. 선택할 수 있는 종류가 하나도 없으면 그 교환권으로는 상품을 받지 못한다. 점원은 손님이 실제로 상품을 고르기 전에, 각 교환권으로 선택할 수 있는 상품 종류가 몇 개인지 안내하려고 한다. 이를 위해 Q장의 교환권 금액을 차례로 확인한다. 이 확인 과정에서는 상품을 판매하거나 재고를 줄이지 않는다. 모든 상품은 각 확인 시점에 선택할 수 있는 상태라고 가정하므로, 앞선 교환권의 금액이나 안내 결과가 뒤의 결과에 영향을 주지 않는다. 같은 금액의 교환권이 여러 번 등장하면 매번 같은 기준으로 종류 수를 계산한다. 상품 가격은 입력에 정렬되지 않은 순서로 주어질 수 있다. 출력은 상품 가격의 순서와 관계없이, 교환권이 주어진 순서를 따라야 한다. 각 교환권에 대해 가격이 그 금액 이하인 상품 종류의 수를 구하는 프로그램을 작성한다. 어떤 상품도 선택할 수 없다면 0을 출력하고, 모든 상품을 선택할 수 있다면 N을 출력한다. 여러 상품의 가격이 같은 경우에도 대표 상품 하나만 세지 않도록 주의한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. (1 ≤ N, Q ≤ 60,000)
둘째 줄에 N개 상품의 가격 P_1, P_2, ..., P_N이 공백으로 구분되어 주어진다. (1 ≤ P_i ≤ 99)
다음 Q개 줄에 교환권 금액 M이 하나씩 주어진다. (0 ≤ M ≤ 99)
입력에 등장하는 모든 수는 정수다.

출력

각 교환권으로 선택할 수 있는 상품 종류의 수를 입력 순서대로 한 줄에 하나씩 출력한다.

5 4
7 2 7 9 4
0
4
7
99

0
2
4
5

3 3
5 5 5
4
5
6

0
3
3

출처: Devin.KR 자체 제작