#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int a[100001],m,n,val,nr;

int b_search0(int nr){
    int in=1, sf=n;
    int mij;
    while(in<=sf){
        mij=(in+sf)/2;
        if(a[mij]<=nr)
            in=mij+1;
        else sf=mij-1;
    }
    mij=(in+sf)/2;
    if(a[mij]>nr)--mij;
    if(a[mij]==nr)return mij;
    else return -1;
}

int b_search1(int nr){
    int in=1, sf=n;
    int mij;
    while(in<sf){
        mij=(in+sf)/2;
        if(a[mij]<=nr)
            in=mij+1;
        else sf=mij;
    }
    mij=(in+sf)/2;
    if(a[mij]>nr)--mij;
    return mij;
}
int b_search2(int nr){
    int in=1, sf=n;
    int mij;
    while(in<sf){
        mij=(in+sf)/2;
        if(a[mij]>=nr)
            sf=mij;
        else in=mij+1;
        //cout<<mij<<'\n';
    }
    mij=(in+sf)/2;
    if(a[mij]<nr)++mij;
    return mij;
}

int main(){
    f>>n;
    for(int i=1; i<=n; ++i)
        f>>a[i];
    f>>m;
    for(int i=1; i<=m; ++i){
        f>>val>>nr;
        if(val==0)g<<b_search0(nr);
        if(val==1)g<<b_search1(nr);
        if(val==2)g<<b_search2(nr);
        g<<'\n';
    }
    return 0;
}