#include<stdio.h>
FILE*fin,*fout;
int i,j,n,v[100004],t,x,nr;
int caut0(int x){
int p,u,m,k;
   p=1;u=n;k=-1;
   while(p<=u){
   m=p+(u-p)/2;
   if(v[m]>x){u=m-1;}
   else
   if(v[m]<x){p=m+1;}
   else if(v[m]==x){k=m;p=m+1;}

   }

return k;
}


int caut1(int x){
int u,p,m,k;
    p=1;u=n;
   while(p<=u){
   m=(p+u)/2;
   if(v[m]>x){u=m-1;}
   else{p=m+1;k=m;}

   }

return k;




}



int caut2(int x){
int p,u,m,k;
    p=1;u=n;
   while(p<=u){
   m=(u+p)/2;
   if(v[m]>=x){u=m-1;k=m;}
   else{p=m+1;}

   }

return k;




}

int main(){
fin=fopen("cautbin.in","r");
fout=fopen("cautbin.out","w");
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%d",&v[i]);

}
int ok;
fscanf(fin,"%d",&nr);
for(i=1;i<=nr;i++){
ok=0;
fscanf(fin,"%d %d",&t,&x);
if(t==0){
       ok=caut0(x);
fprintf(fout,"%d\n",ok);
}
else
if(t==1){
ok=caut1(x);
fprintf(fout,"%d\n",ok);
}
else
if(t==2){
ok=caut2(x);
fprintf(fout,"%d\n",ok);

}

}
fclose(fin);
fclose(fout);

return 0;}