#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int N,v[100001],Q,tip,x;
int cbzero(int x){
    int st=1,dr=N,mij;
    while(st<dr) {
        mij=(st+dr)/2;
        if(v[mij]<=x) st=mij+1;
        else dr=mij;
    }
    st--;
    if(v[st]==x) return st;
    else return -1;
}
int cbunu(int x){
    int st=1,dr=N,mij;
    while(st<dr) {
        mij=(st+dr)/2;
        if(v[mij]<=x) st=mij+1;
        else dr=mij;
    }
    st--;
    return st;

}
int cbdoi(int x){
    int st=1,dr=N,mij;
    while(st<dr) {
        mij=(st+dr)/2;
        if(v[mij]<x) st=mij+1;
        else dr=mij;
    }
    return st;
}
int main()
{
    in>>N;
    for(int i=1;i<=N;i++)   in>>v[i];
    in>>Q;
    for(int i=1;i<=Q;i++){
        in>>tip>>x;
        if(tip==0) out<<cbzero(x)<<'\n';
        if(tip==1) out<<cbunu(x)<<'\n';
        if(tip==2) out<<cbdoi(x)<<'\n';
    }
    return 0;
}