//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
const int Max=100005;
int n,m,v[Max];
int cautbin0(int x)
{
    int st=1,dr=n,poz=0;
  bool ok=0;
  while(st<=dr)
  {
      int mij=(st+dr)/2;
      if(v[mij]==x)
      {
          ok=1;
          poz=mij;
          st=mij+1;

      }
      else if(x<v[mij])
          dr=mij-1;
          else
            st=mij+1;

  }
  if(ok==0)
    return -1;
    return poz;
}
int cautbin1(int x)
{
   int st=1,dr=n,poz=0;
   while(st<=dr)
   {
       int mij=(st+dr)/2;
         if(v[mij]<=x)
        {
           poz=mij;
           st=mij+1;
        }
        else
            dr=mij-1;
   }
   return poz;

}
int cautbin2(int x)
{
     int st=1,dr=n,poz=0;
     while(st<=dr)
     {
         int mij=(st+dr)/2;
         if(v[mij]>=x)
         {
             poz=mij;
             dr=mij-1;
         }
         else
            st=mij+1;
     }
}
void citire()
{
    in>>n;
    for(int i=1;i<=n;i++)
    in>>v[i];
    in>>m;
    for(int i=1;i<=m;i++)
    {
        int p,x; in>>p>>x;
        if(p==0)
        out<<cautbin0(x)<<"\n";
        else if(p==1)
            out<<cautbin1(x)<<"\n";
        else
            out<<cautbin2(x)<<"\n";
    }
}
int main()
{
    citire();
    return 0;
}