#include <stdio.h>
#include <stdlib.h>

int caut_bin_0(int n,int x,int v[100001]){
  int st,dr,m;
  st=1;
  dr=n;
  while(st<dr){
    m=(st+dr)/2;
    if(v[m]>x){
      dr=m;
    }else{
      st=m+1;
    }
  }
  st--;

  if(v[st]==x){
    return st;
  }else{
    return -1;
  }
}
int caut_bin_1(int n,int x,int v[100001]){
  int st,dr,m;
  st=1;
  dr=n;
  while(st<dr){
    m=(st+dr)/2;
    if(v[m]>x){
      dr=m;
    }else{
      st=m+1;
    }
  }

  if(st==n){
    return st;
  }else{
    return st-1;
  }
}
int caut_bin_2(int n,int x,int v[100001]){
  int st,dr,m;
  st=1;
  dr=n;
  while(st<dr){
    m=(st+dr)/2;
    if(v[m]>=x){
      dr=m;
    }else{
      st=m+1;
    }
  }

  return st;
}

int v[100001];

int main(){
  int n,i,m,x,a;
  FILE *fin,*fout;
  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]);
  }
  fscanf(fin,"%d",&m);
  for(i=1;i<=m;i++){
    fscanf(fin,"%d%d",&a,&x);
    if(a==0){
      fprintf(fout,"%d\n",caut_bin_0(n,x,v));
    }else{
      if(a==1){
        fprintf(fout,"%d\n",caut_bin_1(n,x,v));
      }else{
        fprintf(fout,"%d\n",caut_bin_2(n,x,v));
      }
    }
  }


  fclose(fin);
  fclose(fout);
  return 0;
}