/*#include<stdio.h>
typedef struct
{
char name[100];
int time;
}abc;
int main()
{
abc s[101],temp;
int n,i,j, y, m, d;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s %d %d %d",s[i].name,&y,&m,&d);
s[i].time=y*10000+m*100+d;
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(s[j].time>s[j+1].time)
{
temp=s[j];
s[j]=s[j+1];
s[j+1]=temp;
}
else if(s[j].time==s[j+1].time)
{
if(strcmp(s[j].name,s[j+1].name)>0)
{
temp=s[j];
s[j]=s[j+1];
s[j+1]=temp;
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%s\n",s[i].name);
}
}
arr[i] :i가 입력된 횟수
i=0 ~10만
i를 arr[i]번 출력
ex) arr[6]= 2
6 6
*/
/*
#include<stdio.h>
int main()
{
int a[100001]={},n,i,j,b;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&b);
a[b]++;
}
for(i=0;i<=100000;i++)
{
for(j=0;j<a[i];j++)
{
printf("%d ",i);
}
}
}*/
/*#include<stdio.h>
typedef struct
{
int n,g;
}ipchegidong;
int main()
{
ipchegidong m[101],temp;
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&m[i].n,&m[i].g);
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(m[j].n>m[j+1].n)
{
temp=m[j];
m[j]=m[j+1];
m[j+1]=temp;
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d\n",m[i].n,m[i].g);
}
}
pointer : 가리키는 애 ( 주소 )
*/
//int main()
//{
// int a=10;
//
// int* pa = &a;
//
// printf("a = %d\n",a); //직접 참조
// printf("&a = %d\n",&a);
// printf("pa = %d\n",pa);
// printf("*pa = %d\n",*pa); //간접 참조
//}
/*
#include <stdio.h>
void f(int* pa)
{
(*pa)++;
}
int main()
{
int a=10;
f(&a);
printf("%d",a);
return 0;
}
/*
포인터
#include <stdio.h>
void myswap(int*pa,int*pb)
{
int temp;
if((*pa)>(*pb))
{
temp=(*pa);
(*pa)=(*pb);
(*pb)=temp;
}
}
main()
{
int a, b;
scanf("%d%d", &a, &b);
myswap(&a, &b);
printf("%d %d", a, b);
}
binary search
이진,이분 탐색, 검색
*/
#include <stdio.h>
int arr[1000001];
// arr[s] ~ arr[e]에서 k 의 위치를 리턴, 없다면 -1리턴
int bs(int s, int e, int k)
{
int mid = (s+e)/2;
//재귀함수 종료조건 (k가 없다면)
if(arr[mid]==k) return mid;
else if(s==e&& (mid==s||mid==e))return -1;
else if(arr[mid]>k) bs(s,mid-1,k);
else if(arr[mid]<k) bs(mid+1,e,k);
}
int main(){
int n,m,i,k;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d",&k);
int find = bs(1,n,k); // arr[1] ~ arr[n]에서 k 의 위치를 리턴
printf("%d ",find);
}
}