#include<iostream>
#include<fstream>
using namespace std;
int main()
{
  ifstream f("cautbin.in");
  ofstream g("cautbin.out");
  int n,m,v[10020];
  f>>n;
  for(int i=1;i<=n;i++)
    f>>v[i];
  f>>m;
  int x,y;
  while(f>>x>>y)
  {
      int poz=n+1,st=1,dr=n,m;
    if(x==0)
    {
     while(dr>=st)
     {
         m=(st+dr)/2;
      if(v[m]>y)
        dr=m-1;
      if(v[m]<=y)
      {st=m+1;poz=m;}
     }
     if(v[poz]!=y)
        poz=-1;
     g<<poz<<endl;
    }
    if(x==1)
    {
        while(dr>=st)
     {
      m=(st+dr)/2;
      if(v[m]>y)
        dr=m-1;
      if(v[m]<=y)
      {st=m+1;poz=m;}
      }
     g<<poz<<endl;
    }
    if(x==2)
    {
        while(dr>=st)
     {
        m=(st+dr)/2;
      if(v[m]>=y)
        {dr=m-1;poz=m;}
      if(v[m]<y)
      st=m+1;
     }
     g<<poz<<endl;
     }
    }
}