#include<fstream>
#include<algorithm>
#define nmax 100001
using namespace std;

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

int n, a[nmax];
int m, intrebare, x;
int indice_dr, indice_st;
bool exista_x;

int main(){
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];

    fin >> m;
    for(int i = 1; i <= m; ++i){
        fin >> intrebare >> x;
        exista_x = false;
        indice_dr = -1;
        int st = 1, dr = n;
        while(st <= dr){
            int mij = (st+dr)/2;
            if(a[mij] <= x){
                indice_dr = mij;
                st = mij+1;
            }
            else
                dr = mij-1;
        }
        if(a[indice_dr] == x)
            exista_x = true;
        if(intrebare == 0){
            if(exista_x)
                fout << indice_dr << '\n';
        }
        else if(intrebare == 1)
            fout << indice_dr << '\n';
        else{
            st = 1;
            dr = n;
            while(st <= dr){
                int mij = (st+dr)/2;
                if(x <= a[mij]){
                    indice_st = mij;
                    dr = mij-1;
                }
                else
                    st = mij+1;
            }
            fout << indice_st << '\n';
        }
    }
}