// Infoarena, Arhiva Educationala, Cautarea Binara
#include<iostream>
#include<fstream>
using namespace std;

int binar0(int,int[],int);
int binar1(int,int[],int);
int binar2(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];    //Data Input;

    int M,QIndex,value;
    cin>>M;
    for(int i=1;i<=M;i++){
        cin>>QIndex>>value;
        switch(QIndex){
            case 0: cout<<binar0(N,A,value)<<"\n"; break;
            case 1: cout<<binar1(N,A,value)<<"\n"; break;
            case 2: cout<<binar2(N,A,value)<<"\n"; break;
        }  //End of switch
    }
}

int binar0(int N,int A[100005],int value){
    int st=1,dr=N,mid;
    while(st<=dr){
        mid=(st+dr)/2;
        if(A[mid]<=value) st=mid+1;
        else dr=mid-1;
    }
    if(A[mid]>value) mid--;
    if(A[mid]==value) return mid;
    return -1;
}

int binar1(int N,int A[100005],int value){
    int st=1,dr=N,mid;
    while(st<dr){
        mid=(st+dr)/2;
        if(A[mid]<=value) st=mid+1;
        else dr=mid;
    }
    if(A[mid]>value) mid--;
    return mid;
};

int binar2(int N,int A[100005],int value){
    int st=1,dr=N,mid;
    while(st<dr){
        mid=(st+dr)/2;
        if(A[mid]<value) st=mid+1;
        else dr=mid;
    }
    if(A[mid]<value) mid++;
    return mid;
};