#include<iostream>
//#include<fstream>
using namespace std;

int find0(int[],int,int);
int find1(int[],int,int);
int find2(int[],int,int);

int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    int N,A[100005];
    cin>>N;
    for(int i=1;i<=N;i++) cin>>A[i];

    int M;
    cin>>M;
    int code, value;
    for(int i=1;i<=M;i++){
        cin>>code>>value;
        switch(code){
            case 0: cout<<find0(A,N,value)<<"\n"; break;
            case 1: cout<<find1(A,N,value)<<"\n"; break;
            case 2: cout<<find2(A,N,value)<<"\n"; break;
        }
    }

    return 0;

}

int find0(int A[100005],int N,int x){
    int lo=1;
    int hi=N;
    int mid;
    while( (hi-lo)!=1 ){
            mid=lo+(hi-lo)/2;
            if(x>=A[mid]) lo=mid;
            else hi=mid;
        }
    if(A[hi]==x) return hi;
    if(A[lo]==x) return lo;
    return -1;

}
int find1(int A[100005],int N,int x){
    int lo=1,hi=N,mid;
    while((hi-lo)!=1){
        mid=lo+(hi-lo)/2;
        if(A[mid]<=x) lo=mid;
                 else hi=mid;
    }
    if(A[hi]<=x) return hi;
    return lo;
}
int find2(int A[100005],int N,int x){
    int lo=1,hi=N,mid;
    while((hi-lo)!=1){
        mid=lo+(hi-lo)/2;
        if(A[mid]>=x) hi=mid;
                else  lo=mid;
    }
    if(A[lo]>=x) return lo;
    return hi;
}