#include<iostream>
#include<fstream>

using namespace std;

int two(int x, int no[], int left, int right){
  int mid=left+(right-left)/2;
  while(left<=right){
    if(no[mid]>=x) right--;
    else left++;
  }
  if(x>no[mid]) mid++;
  return mid;
}


int one(int x, int no[], int left, int right){
  int mid;
  while(left<=right){
    mid=left+(right-left)/2;
    if(x>=no[mid]) left++;
    else right--;
  }
  if(x<no[mid]) mid--; 
  return mid;
}


int zero(int x, int no[], int left, int right){
  int mid;
  while(left<=right){
    mid=left+(right-left)/2;
    if(x>=no[mid]) left++;
    else right--;
  }
  if(no[mid]>x) mid--;
  if(no[mid]!=x) return -1;
  return mid;
}

int main(){
ifstream in("cautbin.in"); ofstream out("cautbin.out");
int n,m,c,x,i;
in>>n; 
int no[n+1];
for(i=1;i<=n;i++) in>>no[i];
in>>m;
for(i=1;i<=m;i++) {
  in>>c>>x;
  if(c==0) out<<zero(x,no,1,n)<<"\n";
  if(c==1) out<<one(x,no,1,n)<<"\n";
  if(c==2) out<<two(x,no,1,n)<<"\n";
}

in.close(); out.close();
return 0;
}