#include <cstdio>

const int maxn = 100001;

FILE *in = fopen("cautbin.in","r"), *out = fopen("cautbin.out","w");

int n, m;
int a[maxn];

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", &a[i]);
}

int search1(int what)
{
    int st = 1, dr = n, m = 0, answ = 0;

    while ( st <= dr )
    {
        m = st + ((dr - st) >> 1);

        if ( a[m] > what )
            dr = m - 1;
        else if ( a[m] <= what )
            st = m + 1, answ = m;
    }

    return a[answ] == what ? answ : -1;
}

int search2(int what)
{
    int st = 1, dr = n, m = 0;
    int answ = 0;

    while ( st <= dr )
    {
        m = st + ((dr - st) >> 1);

        if ( a[m] <= what )
            st = m + 1, answ = m;
        else
            dr = m - 1;
    }

    return answ;
}

int search3(int what)
{
    int st = 1, dr = n, m = 0;
    int answ = 0;

    while ( st <= dr )
    {
        m = st + ((dr - st) >> 1);

        if ( a[m] >= what )
            dr = m - 1, answ = m;
        else
            st = m + 1;
    }

    return answ;
}

int main()
{
    read();

    fscanf(in, "%d", &m);

    int x, y;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d", &x, &y);

        if ( x == 0 )
            fprintf(out, "%d\n", search1(y));
        else if ( x == 1 )
            fprintf(out, "%d\n", search2(y));
        else
            fprintf(out, "%d\n", search3(y));
    }

    return 0;
}