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

    while ( st <= dr)
    {
        m = (st + dr)/2;
        if ( v[m] <= x)
            st++;
        else dr--;
    }
    m = ( st + dr )/2;
    while( v[m] > x)
        m--;
    return m;
}
int Binara2 (int x, int st, int dr)
{
    while ( st <= dr )
    {
        m = ( st + dr )/2;
        if ( v[m] > x )
            st++;
        else dr--;
    }
    m = ( st + dr )/2;
    while ( v[m] < x )
        m++;
    return m;
}
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;
}