#include <stdio.h>
#include <stdlib.h>
int cbin0(int v[],int dim,int x){
	int l,h,m;
   for(l=0,h=dim-1;l<=h;){
   	m=l+(h-l)/2;
      if(v[m]<x) l=m+1;
      	else if(v[m]>x) h=m-1;
         		else return m+1;
   }
   return -1;
}
int cbin1(int v[],int dim, int x){
	int i=0,l,h,m;
   for(l=0,h=dim-1;l<=h;){
   	m=l+(h-l)/2;
      if(v[m]<=x){
       i=m;
       l=m+1;
       }
       else if(v[m]>x) h=m-1;
      }
   return i+1;
}
int cbin2(int v[],int dim, int x){
	int i=dim-1,l,h,m;
   for(l=0,h=dim-1;l<=h;){
   	m=l+(h-l)/2;
      if(v[m]<x) l=m+1;
      	else if(v[m]>=x){
                  i=m;
         			h=m-1;
                  }
   }
   return i+1;
}
#define deschidere(cale,mod,f)\
	if((f=fopen(cale,mod))==NULL){\
   	printf("\nNu se poate deschide %s.\n",cale);\
      exit(1);\
      }
#define LMAX 100000
int main(){
	int v[LMAX],x,n,m,i,o;
   FILE *f,*g;
   deschidere("cautbin.in","rt",f);
   deschidere("cautbin.out","wt",g);
   fscanf(f,"%d",&n);
   for(i=0;i<n;i++)
   	fscanf(f,"%d",&v[i]);
   fscanf(f,"%d",&m);
   for(i=0;i<m;i++){
   	fscanf(f,"%d %d",&o,&x);
      switch(o){
      	case 0:
         	fprintf(g,"%d\n",cbin0(v,n,x));
            break;
         case 1:
         	fprintf(g,"%d\n",cbin1(v,n,x));
            break;
         case 2:
         	fprintf(g,"%d\n",cbin2(v,n,x));
      }
   }
   return 0;
}