#include<stdio.h>
#define NM 100005
int v[NM],v1[NM],N;
int caut0(int x)
{
int p=0,u=N-1,m,pok=-1;
while (p<=u)
{
m=(p+u)>>1;
if (x>=v[m])
{
pok=m;
p=m+1;
}
else
u=m-1;
}
if (x==v[pok])
return pok+1;
return -1;
}
int cauta1(int x)
{
int p=0,u=N-1,m,pok=-2;
while (p<=u)
{
m=(p+u)>>1;
if (x>=v[m])
{
pok=m;
p=m+1;
}
else
u=m-1;
}
return pok+1;
}
int cauta2(int x)
{
int p=0,u=N-1,m,pok=-2;
int step = 0;
while (p<=u)
{
++step;
m= (p +(u-p)>>1 ) + ((p+u)&1);
if (x>=v1[m])
{
//printf("%d <= %d --- %d --- %d %d %d %d %d %d\n",x,v1[m],step,pok,m,p,u,x,v1[m]);
pok=m;
u=m-1;
}
else {
// printf("%d >= %d --- %d --- %d %d %d %d %d %d\n",x,v1[m],step,pok,m,p,u,x,v1[m]);
p=m+1;
}
}
return pok+1;
}
int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&N);
int x,op;
for (int i=0,j=N-1; i<N; ++i,--j) {
scanf("%d",&v[i]);
v1[j] = v[i];
}
int g;
scanf("%d",&g);
while (g--)
{
scanf("%d%d",&op,&x);
if (op==0)
{
printf("%d\n",caut0(x));
continue;
}
if (op==1)
{
printf("%d\n",cauta1(x));
continue;
}
printf("%d\n",cauta2(x));
}
return 0;
}