#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int q,s,cautat,a[100001],x,n,t,y,m;

int cautbin0(){
    q=1;
    s=n;
    while(q<=s){
        cautat=q+(s-q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
    if(a[s]==x) return s;
}
int cautbin1(){
    q=1;
    s=n;
    while(q<=s){
        cautat=q+(s-q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
    return s;
}
int cautbin2(){
    q=1;
    s=n;
    while(q<=s){
        cautat=q+(s-q)/2;
        if(a[cautat]>=x) s=cautat-1;
        else q=cautat+1;
    }
    return q;
}

int main(){
    in>>n;
    for(int i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    for(int i=1;i<=m;i++){
        in>>y>>x;
        if(y==0) out<<cautbin0()<<endl;
        if(y==1) out<<cautbin1()<<endl;
        if(y==2) out<<cautbin2()<<endl;
    }
    return 0;
}