#include <fstream> 

#define NMAX 100001
#define NOT_FOUND -1
 
int N, V[NMAX]; 
 
int bs0(int numar) 
{
    int lo, hi, mij, last = 0; 
     
    for(lo = 1, hi = N; lo <= hi; ) 
    {
        mij = lo + ((hi - lo) >> 1); 
        if(V[mij] <= numar) last = mij, lo = mij + 1; 
        else hi = mij - 1; 
    }
    if(V[last] == numar) return last;
    else return NOT_FOUND; 
}
 
int bs1(int numar) 
{
    int lo, hi, mij, last = 0; 
     
    for(lo = 1, hi = N; lo <= hi; ) 
    {
        mij = lo + ((hi - lo) >> 1); 
        if( V[mij] <= numar) last = mij, lo = mij + 1; 
        else hi = mij - 1; 
    }
    return last; 
}
 
int bs2(int numar) 
{
    int lo, hi, mij, last = 0; 
     
    for(lo = 1, hi = N; lo <= hi; ) 
    {
        mij = lo + ((hi - lo) >> 1); 
        if(V[mij] >= numar) last = mij, hi = mij - 1; 
        else lo = mij + 1; 
    }
    return last; 
}
     
int main()  
{
    std::ifstream in("cautbin.in"); 
    std::ofstream out("cautbin.out"); 

    int M, i, cod, nr; 
     
    in >> N; 
    for(i = 1; i <= N; i++) in >> V[i]; 

    in >> M; 
    for(i = 1; i <= M; i++)
    {
        in >> cod >> nr; 
        switch(cod)
        {
            case 0 : out << bs0(nr) << '\n'; break;
            case 1 : out << bs1(nr) << '\n'; break;
            case 2 : out << bs2(nr) << '\n'; break; 
        }
    }

    return 0;
}