Sort 마스터 배지훈의 후계자

면접 대비

시간 제한2초메모리 제한512 MB

요약

배열 A를 오름차순으로 정렬해 B를 만들고, 각 질의 D에 대해 B에서 D가 처음 나타나는 위치를 출력하며 없으면 -1을 출력한다.

난이도: 쉬움10점 중 3점
유형: 정렬, 이분 탐색, 배열
정답자: 아직 제출이 없습니다

문제

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에서 후계자를 고르기 위해 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 $N$ 개의 원소를 가진 배열 $A$ 를 주고, $A$ 의 원소들을 오름차순으로 정렬한 배열 $B$ 를 만들게 한다. 그다음 $M$ 개의 질문을 한다. 각 질문에는 정수 $D$ 가 주어진다. 제자들은 주어진 정수 $D$ 가 $B$ 에서 가장 먼저 등장한 위치를 출력하면 된다. 단, $D$ 가 $B$ 에 존재하지 않는 경우에는 -1을 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

입력

첫째 줄에 배열 $A$ 의 원소의 개수 $N$ 과 질문의 개수 $M$ 이 공백으로 구분되어 주어진다.

다음 줄부터 $N$ 줄에 걸쳐 정수 $A_0, A_1, ... , A_{N-1}$ 이 주어진다.

다음 줄부터 $M$ 줄에 걸쳐 정수 $D$ 가 주어진다.

출력

$M$ 개의 질문에 대해서 주어진 $D$ 가 $B$ 에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1을 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)

제한

1 ≤ $N$ ≤ 2×10^5
1 ≤ $M$ ≤ 2×10^5
-10^9 ≤ $A_i$ ≤ 10^9
-10^9 ≤ $D$ ≤ 10^9

예제2

예제 1
입력
```
5 5
9
0
-1
3
2
-1
10
5
9
0
```
예상 출력
```
0
-1
-1
4
1
```
예제 2
입력
```
8 4
3
3
4
9
2
5
3
4
3
10
4
2
```
예상 출력
```
1
-1
4
0
```