#include <stdio.h>
#include <stdlib.h>
inline int cbin0(int v[],int dim,int x){
	int i;
   i=0;
   while(v[i]<=x && i<dim) i++;
   if(v[i-1]==x) return i;
   	else return -1;
}
inline int cbin1(int v[],int dim, int x){
	int i;
   i=0;
   while(v[i]<=x && i<dim) i++;
   return i;
}
inline int cbin2(int v[],int dim, int x){
	int i;
   i=dim-1;
   while(v[i]>=x && i>=0) i--;
   return i+2;
}
#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;
}