#include <iostream>
#include <fstream>

using namespace std;

int a[100001],n,m,i,s,d,ce,val,in;

int cauta1(int vl){
  s=1;d=n;
  while(s<d){
    m=(s+d+1)/2;
    if(a[m]<=vl)s=m;
    else d=m-1;
  }
  if(a[s]==vl)return s;
  else return -1;
}

int cauta2(int vl){
  s=1;d=n;
  while(s<d){
    m=(s+d+1)/2;
    if(a[m]>vl)d=m-1;
    else s=m;
  }
  return s;
}

int cauta3(int vl){
  s=1;d=n;
  while(s<d){
    m=(s+d)/2;
    if(a[m]<vl)s=m+1;
    else d=m;
  }
  return s;
}

int main()
{
    ifstream f ("cautbin.in");
    ofstream g ("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)f>>a[i];
    f>>in;
    for(i=1;i<=in;i++){
      f>>ce>>val;
      if(ce==0) g<<cauta1(val);
      else if(ce==1) g<<cauta2(val);
      else g<<cauta3(val);
      g<<'\n';
    }
    f.close ();
    g.close ();
    return 0;
}