#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int x[100001];
int caut_bin(int val,int st,int dr){
    int max=-1;
    while(st<=dr){
        int med=(st+dr)/2;
        if(x[med]<=val){
            if(med>max){
                st=med+1;
                max=med;
            }
        }
        else{
            dr=med-1;
        }
    }
    return max;
}
int caut_bin2(int val,int st,int dr){
    int min=100000000;
    while(st<=dr){
        int med=(st+dr)/2;
        if(x[med]>=val){
            if(med<min){
                min=med;
                dr=med-1;
            }
        }
        else{
            st=med+1;
        }
    }
    return min;
}
int main()
{
    int n;
    f>>n;
    for(int i=1;i<=n;i++){
        f>>x[i];
    }
    int m;
    f>>m;
    int y,z;
    for(int i=1;i<=m;i++){
        f>>y>>z;
        if(y==1){
            g<<caut_bin(z,1,n)<<"\n";
        }
        if(y==2){
            g<<caut_bin2(z,1,n)<<"\n";
        }
        else if(y==0){
            int aux=caut_bin(z,1,n);
            if(x[aux]==z){
                g<<aux<<"\n";
            }
            else{
                g<<-1<<"\n";
            }
        }
    }
    return 0;
}