#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=1,dr=n,mij,nr=-1;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij]==x)
        {
            nr=mij;
            st=mij+1;
        }
        else
            if (v[mij]<x)
                st=mij+1;
            else
                dr=mij-1;
    }
    return nr;

}

int binara2(int x)
{
 int st=1,dr=n,mij,nr=-1;
    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=-1;
    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;
}