#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,m,v[100000],x;
int cautbin(int x)
{
 int st=1,dr=n,mij;
 do{
    mij=st+(dr-st)/2;
    if(v[mij]==x)
        return mij;
    if(v[mij]>x)
      dr=mij-1;
    if(v[mij]<x)
      st=mij+1;
    }
    while(st<=dr);
   return -1;
 }
int cautbin1(int x)
{
 int st=1,dr=n,mij;
 do{
    mij=st+(dr-st)/2;
    if(v[mij]==x)
       {
        while(v[mij]==x)
             mij++;
        return mij-1;
        }
    if(v[mij]>x)
      dr=mij-1;
    if(v[mij]<x)
      st=mij+1;
    }
    while(st<=dr);
   return -1;
 }

int cautbin2(int x)
{
 while(cautbin1(x)==-1)
      x--;
 return cautbin1(x);
 }

 int cautbin3(int x)
 {while(cautbin(x)==-1)
       x++;
  int mij=cautbin(x);
  while(v[mij]==x)
      mij--;
      return mij+1;

  }

 int main()
 {
  int i,x,ef;
  in>>n;
  for(i=1;i<=n;i++)
  in>>v[i];
  in>>m;
  for(i=1;i<=m;i++)
  {
   in>>ef>>x;
   if(ef==0)
     out<<cautbin1(x)<<"\n";
     else if(ef==1)
             out<<cautbin2(x)<<"\n";
             else out<<cautbin3(x)<<"\n";
   }
  return 0;
  in.close();
  out.close();
   }