#include <iostream>
#include <fstream>

using namespace std;

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

int n;
unsigned int v[100005];

int zero(int x){
    int st=1;
    int dr=n;
    int r=-1;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(v[mij]<x){
            st=mij+1;
        }
        else if(v[mij]==x){
            r=mij;
            st=mij+1;
        }
        else{
                dr=mij-1;

        }
    }
    return r;
}
int unu(int x){
    int st=1,dr=n,r=-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<=x){
            st=mij+1;
            r=mij;
        }
        else{
            dr=mij-1;
        }
    }
    return r;
}
int doi(int x){
    int st=1,dr=n,r=-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]>=x){
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return r;

}


int main()
{
    int i,nr_i,in;
    unsigned int x;
    in >> n;
    for(i=1;i<=n;i++){
        in >> v[i];
    }
    in >> nr_i;
    for(i=1;i<=nr_i;i++){
        in >> in;
        in >> x;
        if(in==0)
            out << zero(x) << endl;
        else if(in==1)
            out << unu(x) << endl;
        else if(in==2)
            out << doi(x) << endl;
    }

}