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

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

int N,A[100005];


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

    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;

        if(code==0) cout<<find0(A,N,value)<<"\n";
        else if(code==1) cout<<find1(A,N,value)<<"\n";
              else if(code==2) cout<<find2(A,N,value)<<"\n";

    }

    return 0;

}

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

    if(A[lo]==x) return lo;
    if(A[lo-1]==x) return lo-1;
    if(A[hi]==x) return hi;
    return -1;

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