#include<fstream>
#include<math.h>
using namespace std;
int cutbin0(long long int x,long long int v[],long long int k ){
    long long int l=0;
    for(long long int i=k;i>0;i/=2){
        long long int c=pow(2,i);
        if(v[l+c]<=x){
            l+=c;
        }
    }
    if(v[l]==x){
        return l;
    }else{
        return -1;
    }
}
int cutbin1(long long int x,long long int v[],long long int k ){
    long long int l=0;
    for(long long int i=k;i>0;i/=2){
        long long int c=pow(2,i);
        if(v[l+c]<=x){
            l+=c;
        }
    }
    return l;
}
int cutbin2(long long int x,long long int v[],long long int k,long long int n ){
    long long int l=n;
    for(long long int i=k;i>0;i/=2){
        long long int c=pow(2,i);
        if(v[l-c]>=x){
            l-=c;
        }
    }
    return l;
}
int main(){
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    long long int n,t;
    fin>>n;
    long long int v[100000];
    for(long long int i=1;i<=n;i++){
        fin>>v[i];
    }
    fin>>t;
    long long int s,y;
    for(long long int i=1;i<=n;i++){
        fin>>s>>y;
        if(s==0){
            fout<<cutbin0(y,v,log2(n))<<"\n";
        }
        if(s==1){
            fout<<cutbin1(y,v,log2(n))<<"\n";
        }
        if(s==2){
            fout<<cutbin2(y,v,log2(n),n)<<"\n";
        }
    }
}