#include <bits/stdc++.h>

using namespace std;

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

int arr[100005];
int n, m;
int t, x;
int st, dr, mid;

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 )
        {
            st = 1;
            dr = n;
            while( st <= dr )
            {
                mid = st + (dr - st)/2;

                if( arr[mid] <= x )
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            mid = st + (dr - st)/2;

            if( arr[mid] > x )
                mid--;

            if( arr[mid] == x )
                out<<mid<<"\n";
            else
                out<<-1;
        }

        if( t == 1 )
        {
            st = 1;
            dr = n;
            while( st <= dr )
            {
                mid = st + (dr - st)/2;

                if( arr[mid] <= x )
                    st = mid + 1;
                else
                    dr = mid -1;
            }

            mid = st + (dr - st)/2;

            if( arr[mid] > x )
                mid--;

            out<<mid<<"\n";
        }

        if( t == 2 )
        {
            st = 1;
            dr = n;
            while( st <= dr )
            {
                mid = st + (dr - st)/2;

                if( arr[mid] < x )
                    st = mid + 1;
                else
                    dr = mid - 1;
            }

            mid = st + (dr - st)/2;

            if( arr[mid] < x )
                mid++;

            out<<mid<<"\n";
        }
    }

    return 0;
}