//pozitia lui x intrun sir sortat
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int main()
{int n,m ,x[100001],in=1,sf,b,a;
fi>>n;
  for (int i=1;i<=n;i++)
  fi>>x[i];
  fi>>m;
  for(int i=1;i<=m;i++){
  fi>>b;
  fi>>a;
  in=1;
  sf=n;
  if(b==0)
  while(in<sf)
  {
      if(x[(in+sf+1)/2]<=a)
        in=(in+sf+1)/2;
      else
        sf=(in+sf+1)/2;
    if(sf==in+1){
        if(x[in]==a)
        fo<<in;
        else
        fo<<-1;
        break;}
    }
    if(b==1)
      while(in<sf)
  {
      if(x[(in+sf+1)/2]<=a)
        in=(in+sf+1)/2;
      else
        sf=(in+sf+1)/2;
    if(sf==in+1){
        if(x[sf]==a)
        fo<<sf;
        if(x[sf]!=a)
        fo<<sf-1;
        break;}
    }
     if(b==2)
  while(in<sf)
  {
      if(x[(in+sf+1)/2]<=a)
        in=(in+sf+1)/2;
      else
        sf=(in+sf+1)/2;
    if(sf==in+1){
        if(x[in]==a)
        fo<<in;
        else
        fo<<in+1;
        break;}
    }
    fo<<'\n';
    }
    return 0;
}