#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int main()
{
  int c,x,st,dr,ans,n,i,q,m;
  fin>>n;
  for(i=1;i<=n;i++){
      fin>>v[i];
  }
  fin>>q;
  for(i=1;i<=q;i++){
      fin>>c>>x;
      st=1;
      dr=n;
      while(st<=dr){
          m=(st+dr)/2;
          if(v[m]>x)
          dr=m-1;
          else
          st=m+1;
      }
      if(c==0){
          if(v[dr]!=x)
          fout<<-1<<'\n';
          else
          fout<<dr<<'\n';
      }
      if(c==1){
          fout<<dr<<'\n';
      }
      else if(c==2){
          st=1;
      dr=n;
      while(st<=dr){
          m=(st+dr)/2;
          if(v[m]>=x)
          dr=m-1;
          else
          st=m+1;
      }
      fout<<st<<'\n';
      }
}
}