#include<iostream>
#include<fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
 int v[100005];

int cautare_binara0(int l, int r, int x)
{
    int mijloc;

    while(l <= r)
    {
        mijloc = ( l + r) / 2;
        if( v[mijloc] <= x)
            l = mijloc + 1;
        else r = mijloc - 1;
    }
    mijloc =  (l + r) / 2;
    if ( v[mijloc] > x) mijloc --;
    if(v[ mijloc] == x) return mijloc;
    else return -1;

}
int cautare_binara1( int l, int r, int x)
{
    int mijloc;

    while(l < r)
    {
        mijloc = ( l + r) / 2;
        if( v[mijloc] <= x)
            l = mijloc + 1;
        else r = mijloc ;
    }
    mijloc = ( l + r) / 2;
    if( v[mijloc] > x)
        mijloc --;
    return mijloc;
}
int cautare_binara2( int l, int r, int x)
{
    int mijloc;

    while(l < r)
    {
        mijloc = ( l + r) / 2;
        if( v[mijloc] < x)
        l = mijloc + 1;
        else r = mijloc ;
    }
    mijloc = ( l + r) / 2;
    if( v[mijloc] < x)
        mijloc ++;
    return mijloc;
}
int main()
{
    int n, m, x, cod, i;
    f >> n;
    for(i = 1; i <=n; i++)
        f >> v[i];
    f >> m;
    for( i = 1; i <= m; i++)
    {
        f >> cod >> x;
        if( cod == 0) g << cautare_binara0( 1, n, x) << '\n';
        else if (cod == 1) g << cautare_binara1( 1, n, x) << '\n';
        else if( cod == 2) g << cautare_binara2( 1, n, x) << '\n';
    }

return 0;

}