/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 9, 2010, 1:31 PM
 */
#include <cstdlib>
#include <fstream>
#define Nmax 100011

/*
 * 
 */
using namespace std;
int main(int argc, char** argv)
{
    int v[Nmax];
    int N, M, i, j, p, idx, tidx, stop;
    ifstream in( "cautbin.in" );
    ofstream out( "cautbin.out" );
    in>>N;
    for( stop=1; stop <= N; stop<<=1 );
    for( i=1; i <= N; in>>v[i], ++i );
    for( in>>M; M; --M )
    {
        in>>i>>j;
        if( i < 2 )
        {
            for( p=0, idx=stop; idx; idx>>=1 )
            {
                tidx=p+idx;
                if( tidx <= N && j >= v[tidx] )
                    p=tidx;
            }
            if( !i && j != v[p] )
                out<<"-1\n";
            else out<<p<<'\n';
        }
        else {
                for( p=N, idx=stop; idx; idx>>=1 )
                {
                    tidx=p-idx;
                    if( tidx >= 1 && j <= v[tidx] )
                        p=tidx;
                }
                out<<p<<'\n';
            }
    }
    return EXIT_SUCCESS;
}