#include <iostream>
#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,k,x,v[100001],intrebare;
int binara1(int x)
{
   int st,dr,mij;
   st=1;
   dr=n;
   while(st<=dr)
   {
       mij=(st+dr)/2;
       if(v[mij]==x && v[mij+1]!=x)
         return mij;
       else
        if(x<v[mij])
            dr=mij-1;
       else
        st=mij+1;
   }
   if(v[st]==x)
      return st;

   return -1;

}

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

int binara3(int x)
{
    int st,dr,mij,nr;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
           {
               nr=mij;
               dr=mij-1;
           }
           else
            st=mij+1;
    }

     return nr;
}


int main()
{
f>>n;
for(i=1;i<=n;i++)
    f>>v[i];

f>>k;
for(i=1;i<=k;i++)
{
    f>>intrebare>>x;
    if(intrebare==0)
        g<<binara1(x)<<endl;
    if(intrebare==1)
        g<<binara2(x)<<endl;
    if(intrebare==2)
        g<<binara3(x)<<endl;
}

    return 0;
}