#include<fstream.h>

using namespace std;

int main()
{
int max=0,st,dr,mij,poz,N,v[100000],x,i,E,y,z,M;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

  f>>N;
for(i=1;i<=N;i++)
  f>>v[i];
  f>>M;
dr=N+1;
st=0;
mij=(dr+st)/2;
 for(;M>0;M--)
  {f>>E;
   f>>x;
  while(st+1<dr)
   {
     if(x<v[mij])
     {dr=mij;
      mij=(dr+st)/2;
     }
     if(x>=v[mij])
    {st=mij;
     mij=(dr+st)/2;
    }
   }
   if(E==0)
   {if(x==v[mij])
   {
   while(x==v[mij+1])
   {
   mij=mij+1;
   }
   g<<mij<<endl;
   }
   else
   g<<-1<<endl;
   }
   if(E==1)
   {
   if(x==v[mij])
   {
   while(x==v[mij+1])
   {
   mij=mij+1;
   }
   g<<mij<<endl;
   }
   else
   {
   y=v[st];
   while(y==v[st+1])
   st=st+1;
   g<<st<<endl;
   }
   }
   if(E==2)
   {
   if(x==v[mij])
   {while(x==v[mij-1])
   mij=mij-1;
   g<<mij<<endl;
   }
   else
   {
   z=v[dr];
   while(z==v[dr-1])
   dr=dr-1;
   g<<dr<<endl;
   }
   }
   }
f. close();
g. close();
}