#include <iostream>
#include <fstream>


using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,v[100100],k;

int bs0(int x)
{
    int i=1,j=n,m;

    while (i<=j)
    {    m=(i+j)/2;

        if (v[m]<=x)
            i=m+1;
        else j=m-1;
    }
   i--;
   if (v[i]==x)
    return i;
   return -1;
}

int bs1(int x)
{


    int i=1,j=n,m;

    while (i<=j)
    {    m=(i+j)/2;

        if (v[m]<=x)
            i=m+1;
        else j=m-1;
    }
   i--;

   return i;
}


int bs2( int x)
{
    int st, dr, m;
    st = 1;
    dr = n;
    while (st<dr)
    {
        m = (st+dr)/2;
        if (v[m]>=x)
            dr = m;
        else
            st = m+1;
    }
    return st;
}


int main()
{  int q,x,l;
    f>>n;
    for (int i=1;i<=n;i++)
        f>>v[i];
    f>>l;
    for (int i=1;i<=l;i++)
    {
        f>>q>>x;
        if (q==0)
            g<<bs0(x);
        else if (q==1)
            g<<bs1(x);
        else g<<bs2(x);
        g<<endl;
    }
}