#include <bits/stdc++.h>
using namespace std;

ifstream in ("cautbin.in");
ofstream out ("cautbin.out");

int n, m, t, x;
int arr[100005];

int cautBinar0( int st,int dr, int val )
{
    if( st > dr )
        if( arr[dr] == val )
            return dr;
        else
            return -1;

    int mid = (st + dr)/2;

    if( arr[mid] <= val )
        return cautBinar0( mid + 1, dr, val );
    else
        return cautBinar0( st, mid - 1, val );
}

int cautBinar1( int st, int dr, int val )
{
    if( st > dr )
        if( arr[st] > val )
            return st - 1;
        else
            return st;

    int mid = (st + dr)/2;

    if( arr[mid] <= val )
        return cautBinar1( mid + 1, dr, val );
    else
        return cautBinar1( st, mid - 1, val );
}


int cautBinar2( int st, int dr, int val )
{
    if( st > dr )
        return st;

    int mid = (st + dr)/2;

    if( arr[mid] < val )
        return cautBinar2( mid + 1, dr, val );
    else
        return cautBinar2( st, mid - 1, val );
}

int main()
{
    in>>n;
    for( int i = 1; i <= n; i++ )
        in>>arr[i];

    in>>m;
    for( int i = 1; i <= m; i++ )
    {
        in>>t>>x;

        if( t == 0 )
            out<<cautBinar0( 1, n, x )<<"\n";
        else if( t == 1 )
            out<<cautBinar1( 1, n, x )<<"\n";
        else
            out<<cautBinar2( 1, n, x )<<"\n";
    }

    return 0;
}