#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMAX=100000;
int v[NMAX+5];
int n;
int cautare_binara0(int x)
{
    int m, st, dr, sol=-1;
    st=1;
    dr=n;
    while(st<=dr)
    {
      m=(st+dr)/2;
      if(v[m]==x)
      {
          sol=m;
          st=st+1;
      }
      else
      {
        if(v[m]<x)
            st=st+1;
        else
            dr=dr-1;
      }
    }
    return sol;
}
int cautare_binara1(int x)
{
   int m, st, dr, sol=0;
   st=1;
   dr=n;
   while(st<=dr)
   {
       m=(st+dr)/2;
       if(v[m]<=x)
          {
              st=st+1;
              sol=max(m, sol);
          }
       else
          dr=dr-1;

   }
   return sol;
}
int cautare_binara2(int x)
{
    int dr, st, sol=n, m;
    st=1;
    dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]>=x)
        {
            dr=dr-1;
            sol=min(sol, m);
        }
        else
            st=st+1;
    }
    return sol;
}
int main()
{
    int i, m, x, valoare;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>valoare>>x;
        if(valoare==0)
            fout<<cautare_binara0(x)<<"\n";
        if(valoare==1)
            fout<<cautare_binara1(x)<<"\n";
        if(valoare==2)
            fout<<cautare_binara2(x)<<"\n";
    }
    return 0;
}