#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;
}