#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 = li + (ls - li) / 2;
    while( li <= ls){
        if(v[mij] == x){
            while(v[mij] == x)
                mij++;
            --mij;

            return mij;
        }

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

    return -1;
}

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

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

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

    return mij;
}

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