#include <fstream>

using namespace std;
int N,A[100005],k;
int R,L,M;



int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>N;
    for(int i=1;i<=N;++i) f>>A[i];
    f>>k;
    int caz,val;
    while( k-- ){
        f>>caz>>val;
        L=1;R=N;
        if( caz == 0 ){
                while( R - L > 1 )  {     M= (L+R)>>1;
                    if(val<A[M]) R=M-1;
                    else     L=M;   }
                if( A[R] == val ) g<<R;
           else if( A[L] == val ) g<<L;
           else g<<"-1";
       }else if( caz == 1 ){
                while( R - L > 1 )  {   M= (L+R)>>1;
                    if(val<A[M]) R=M-1;
                    else     L=M;   }
                if( A[R] <= val ) g<<R;
           else if( A[L] <= val ) g<<L;
           else g<<"-1";
       }else {
                while( R - L > 1 )  {  M= (L+R)>>1;
                    if(val>A[M]) L=M+1;
                    else     R=M;   }
                if( A[R] >= val ) g<<R;
           else if( A[L] >= val ) g<<L;
           else g<<"-1";
        }
    g<<'\n';
    }
    f.close();
    g.close();

    return 0;
}