10036 이진 탐색 Silver IV

문제

N개의 정수가 오름차순으로 정렬되어 있다. M개의 정수가 주어졌을 때, 각 정수가 배열에서 몇 번째에 위치하는지 출력하는 프로그램을 작성하시오. 위치는 1부터 시작하며, 찾지 못하면 -1을 출력한다.

입력

첫째 줄에 배열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 오름차순으로 주어진다. 각 정수는 절댓값이 1,000,000,000 이하이다. 셋째 줄에 찾을 정수의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 넷째 줄부터 M개의 줄에 찾을 정수가 하나씩 주어진다.

출력

각 정수에 대해 배열에서의 위치를 출력한다. 없으면 -1을 출력한다.

5
1 3 5 7 9
3
5
3
8

3
2
-1