#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,x,v[100001],val,m;
int Binara0(int x, int st, int dr)
{   int mi;
    while (st <= dr)
        {mi = (st + dr)/2;
        if ( v[mi] <= x)
             st = mi + 1;
        else dr = mi - 1;
        }
    mi = (st + dr)/2;
    if ( v[mi] > x)
        mi--;
    if (v[mi] == x)
        return mi;
    return -1;
}
int Binara1(int x, int st, int dr)
{
    int mi;
    while ( st < dr)
    {
        mi = (st + dr)/2;
        if ( v[mi] <= x)
            st = mi + 1 ;
        else dr = mi ;
    }
    mi = ( st + dr )/2;
    if( v[mi] > x)
        mi--;
    return mi;
}
int Binara2 (int x, int st, int dr)
{   int mi;
    while ( st < dr )
    {
        mi = ( st + dr )/2;
        if ( v[mi] < x )
            st = mi + 1;
        else dr = mi;
    }
    mi = ( st + dr )/2;
    if ( v[mi] < x )
        mi++;
    return mi;
}
int main()
{   f >> n;
    for (i=1; i<=n; i++)
        f >> v[i];

    f >> m;
    for (i=1; i<=m; i++)
       {
           f >> val >> x;
           if ( val == 0)
                g << Binara0(x,1,n)<<endl;
           else
            if( val == 1 )
                g << Binara1(x,1,n)<<endl;
            else
                g << Binara2(x,1,n)<<endl;
       }

    return 0;
}