#include <fstream>
#define DMAX 100004
using namespace std;

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

int n;
int v[DMAX];
int nr;

void init();
int caut0(int, int[], int);
int caut1(int, int[], int);
int caut2(int, int[], int);

int main(){
    init();


    fin>>nr;

    int i, x, y;
    for(i = 1; i<= nr; ++i){
        fin>>x>>y;
        if(x == 0) { fout<<caut0(y,v,n)<<'\n'; continue; }
        if(x == 1) { fout<<caut1(y,v,n)<<'\n'; continue; }
        if(x == 2) { fout<<caut2(y,v,n)<<'\n'; continue; }
    }



    return 0;
}

void init(){
    fin>>n;

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


int caut0(int val, int v[], int n){
    int mij, dr = n, st = 1;
    while ( st <= dr){
        mij = (dr+st)/2;
        if(v[mij] <= val) st = mij + 1;
        else dr = mij - 1;
    }

    mij = (dr+st)/2;



    if(v[mij] == val) return mij;
    return -1;
}

int caut1(int val, int v[], int n){
    int mij, dr = n, st = 1;
    while ( st <= dr){
        mij = (dr+st)/2;
        if(v[mij] <= val) st = mij + 1;
        else dr = mij - 1;
    }
    return (dr+st)/2;
}

int caut2(int val, int v[], int n){
    int mij, dr = n, st = 1;
    while ( st <= dr){
        mij = (dr+st)/2;
        if(v[mij] < val) st = mij + 1;
        else dr = mij - 1;
    }
    return (dr+st)/2 +1 ;
}