#1909 Binary search

144  5 s   256 MB  

Description

오름차순 정렬이 된 정수로 이뤄진 배열 $A$가 주어질 때, 임의의 숫자 $X$를 입력받아 $X$가 $A$의 몇번째에 존재하는지 검색하는 프로그램을 작성하라. 검색은 프로그램이 실행되는 동안 여러번 이뤄진다.

 

Input

입력의 첫줄에는 배열의 크기 $N$이 입력되며, 그 다음줄에는 오름차순으로 정렬된 $N$개의 숫자가 입력된다.

다음에는 검색하려는 횟수를 뜻하는 $Q$가 입력되며, 그 다음 부터 $Q$개의 정수가 한줄에 하나씩 입력된다.

제약조건

Output

검색하려는 숫자가 배열 $A$에 존재할 경우 배열 $A$에서의 위치를 출력하며, 그렇지 않을 경우 $-1$을 출력한다. 배열의 맨 앞의 원소의 위치는 0이며, 그다음은 $1, \dots $마지막은 $N$-1이다.

Sample Input

Sample Output

5
1 3 4 5 7
4
4
1
6
8
2
0
-1
-1