Description
오름차순 정렬이 된 정수로 이뤄진 배열 A가 주어질 때, 임의의 숫자 X를 입력받아 X가 A의 몇번째에 존재하는지 검색하는 프로그램을 작성하라.
검색은 프로그램이 실행되는 동안 여러번 이뤄진다.
Input
입력의 첫줄에는 배열의 크기 N이 입력되며, 그 다음줄에는 오름차순으로 정렬된 N개의 숫자가 입력된다.
다음에는 검색하려는 횟수를 뜻하는 Q가 입력되며, 그 다음 부터 Q개의 정수가 한줄에 하나씩 입력된다.
제약조건
-
1 <= N <= 100,000
-
1 <= Q <= 10,000
-
모든 정수는 0 이상 231 - 1 이하의 정수다.
Output
검색하려는 숫자가 배열 A에 존재할 경우 배열 A에서의 위치를 출력하며, 그렇지 않을 경우 -1을 출력한다.
배열의 맨 앞의 원소의 위치는 0이며, 그다음은 1,... 마지막은 N-1이다.