#include <fstream>
#define Nmax 100005

using namespace std;

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

int n,v[Nmax],m,p,x;

int bin0( int x ){
    int li = 1;
    int ls = n;
    int mij ;
    while( li <= ls){
        mij = li + (ls - li) / 2;

        if(v[mij] <= x){
            li = mij + 1;
        }else{
            ls = mij - 1;
        }
    }

    mij = li + ( ls - li ) /2;
    if(v[mij] > x)
        mij -- ;
    if( v[mij] == x)
    return mij;

    return -1;
}

int bin1(int x){
    int li = 1;
    int ls = n;
    int mij = li + (ls - li) / 2;
    while(li < ls){
         mij = li + (ls - li) / 2;

        if(v[mij] <= x){
            li = mij + 1;
        }else{
            ls = mij;
        }
    }

    mij = li + (ls - li) / 2;

    if(v[mij] > x)
        mij--;

    return mij;
}

int bin2(int x){
    int li = 1;
    int ls = n;
    int mij;
    while ( li <= ls ){
        mij = li + (ls - li) / 2;
        if(v[mij] < x){
            li = mij + 1;
        }else{
            ls = mij - 1;
        }
    }
    mij = li + (ls - li) / 2;

    if(v[mij] < x)
        mij++;

    return  mij;

}

int main(){
    int i;
    f >> n;
    for( i = 1 ; i <= n; i++){
        f >> v[i];
    }

    f >> m;
    for( i = 1 ; i <= m ; i++){
        f >> p >> x;

        if( p == 0 ){
            g << bin0 (x) << "\n";
        }else if( p == 1){
                g << bin1 (x) << "\n";
              }else{
                    g << bin2 (x) << "\n";

              }
    }

    return 0;
}