#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");


int main(){

    int N, sN[100002], M, x, intrebare;
    fin >> N;
    
    for( int i = 1 ; i <= N ; ++i ){
        fin >> sN[i];
    }
    
    fin >> M;
    
    for( int fg = 1 ; fg <= M ; ++fg ){
        fin >> intrebare >> x;
        
        if( intrebare == 0 ){
            
            int st = -1, dr = N, mid;
            while( dr - st > 1 ){
                mid = st + (dr - st) / 2;
                if( x < sN[mid] ) dr = mid;
                else st = mid;
            }
            
            if( sN[N] == x ) fout << N;
            else if( st == N || sN[st] != x ){
                
                fout << -1;
                
            }else fout << st;
            
        }else if (intrebare == 1){
            
            int st = -1, dr = N, mid;
            while( dr - st > 1 ){
                mid = st + (dr - st) / 2;
                if( x < sN[mid] ) dr = mid;
                else st = mid;
            }
            
            if( sN[N] <= x) fout << N;
            else fout << st;
            
        }else if( intrebare == 2 ){
            
            int st = -1, dr = N, mid;
            while( dr - st > 1 ){
                mid = st + (dr - st) / 2;
                if( x > sN[mid] ) st = mid;
                else dr = mid;
            }
            
            
            if( dr == N || sN[dr] != x ){
                if( dr == N && sN[dr] == x ) fout << dr;
                else fout << st;
            }else fout << dr;
            
            
        }
        
    }
    
}