#include <iostream>
#include <fstream>
using namespace std;

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

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

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

int main(){
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n;
    fin>>n;
    int v[n];
    for (int i=0; i<n; ++i)
        fin>>v[i];
    int m;
    fin>>m;
    short int tip;
    int nr;
    for (int i=0; i<m; ++i){
        fin>>tip>>nr;
        switch (tip){
            case 0: fout<<cautare_binara1(v,nr,n)<<'\n';
                break;
            case 1: fout<<cautare_binara2(v,nr,n)<<'\n';
                break;
            case 2: fout<<cautare_binara3(v,nr,n)<<'\n';
                break;
        }
    }
}